public class Solution {    public int FindTargetSumWays(int[] nums, int S) {        Queue
     
       Q = new Queue
      
       ();            Q.Enqueue(0);            var count = 0;            var dic = new Dictionary
       
        ();            var dic2 = new Dictionary
        
         ();            for (int i = 0; i < nums.Length; i++)            {                var num = nums[i];                dic2.Clear();                foreach (var d in dic)                {                    dic2.Add(d.Key, d.Value);                }                dic.Clear();                while (Q.Count > 0)                {                    var n = Q.Dequeue();                    var N = 1;                    if (dic2.ContainsKey(n))                    {                        N = dic2[n];                    }                    if (!dic.ContainsKey(n + num))                    {                        dic.Add(n + num, N);                    }                    else                    {                        dic[n + num] += N;                    }                    if (!dic.ContainsKey(n - num))                    {                        dic.Add(n - num, N);                    }                    else                    {                        dic[n - num] += N;                    }                }                foreach (var l in dic.Keys)                {                    if (l == S && i == nums.Length - 1)                    {                        count = dic[l];                    }                    else                    {                        Q.Enqueue(l);                    }                }            }            return count;    }}
        
       
      
     

补充一个python的实现：

1 class Solution: 2     def findTargetSumWays(self, nums: 'List[int]', S: 'int') -> int: 3         s = {
   0:1} 4         s2 = {} 5         for n in nums: 6             for x in s.keys(): 7                 x1 = x + n 8                 x2 = x - n 9                 if x1 in s2.keys():10                     s2[x1]=s2[x1]+s[x]11                 else:12                     s2[x1]=s[x]13                 if x2 in s2.keys():14                     s2[x2]=s2[x2]+s[x]15                 else:16                     s2[x2]=s[x]17             #s.clear()18             s = s2.copy()19             s2.clear()20         if S in s.keys():21             return s[S]22         else:23             return 0

这道题的主要思想是利用字典存储之前的已经计算过的值，但是做题的时候状态不太好，所以写了很久。

做算法题，头脑不清醒的时候，效率很低，应该休息，把状态调整好再做。

简单介绍一下本题的思路，举例数据nums=[1, 1, 1, 1, 1]， S=3。

初始情况下字典s为{0:1}，表示值0出现过1次。

遍历nums，取每一个值进行计算，i为遍历的下标：

i=0时，当前值为1，得到0+1和0-1，因此s={1: 1, -1: 1}

i=1时，当前值为1，在之前的基础上分别计算+1和-1，有1+1==2，1-1==0，-1+1==0，-1-1==-2，因此s={2: 1, 0: 2, -2: 1}

i=2时，在之前基础上继续计算每一个值+1和-1，得到s={3: 1, 1: 3, -1: 3, -3: 1}

i=3时，s={4: 1, 2: 4, 0: 6, -2: 4, -4: 1}

i=4时，s={5: 1, 3: 5, 1: 10, -1: 10, -3: 5, -5: 1}

遍历完毕，目标S=3，则s[3]的值是5，表示有5种情况可以得到运算结果为3。