public class Solution {
public int FindTargetSumWays(int[] nums, int S) {
Queue<int> Q = new Queue<int>();
Q.Enqueue();
var count = ;
var dic = new Dictionary<int, int>();
var dic2 = new Dictionary<int, int>();
for (int i = ; 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 > )
{
var n = Q.Dequeue();
var N = ;
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 - )
{
count = dic[l];
}
else
{
Q.Enqueue(l);
}
}
}
return count;
}
}https://leetcode.com/problems/target-sum/#/description
补充一个python的实现：
class Solution:
def findTargetSumWays(self, nums: 'List[int]', S: 'int') -> int:
s = {:}
s2 = {}
for n in nums:
for x in s.keys():
x1 = x + n
x2 = x - n
if x1 in s2.keys():
s2[x1]=s2[x1]+s[x]
else:
s2[x1]=s[x]
if x2 in s2.keys():
s2[x2]=s2[x2]+s[x]
else:
s2[x2]=s[x]
#s.clear()
s = s2.copy()
s2.clear()
if S in s.keys():
return s[S]
else:
return
这道题的主要思想是利用字典存储之前的已经计算过的值，但是做题的时候状态不太好，所以写了很久。
做算法题，头脑不清醒的时候，效率很低，应该休息，把状态调整好再做。
简单介绍一下本题的思路，举例数据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。