public class Solution {
public int SubarraySum(int[] nums, int k) {
int sum = , result = ;
Dictionary<int, int> preSum = new Dictionary<int, int>();
preSum.Add(, );
for (int i = ; i < nums.Length; i++)
{
sum += nums[i];
if (preSum.ContainsKey(sum - k))
{
result += preSum[sum - k];
}
if (preSum.ContainsKey(sum))
{
preSum[sum]++;
}
else
{
preSum.Add(sum, );
}
}
return result;
}
}https://leetcode.com/problems/subarray-sum-equals-k/#/solutions
补充一个python的实现，和上面的思路一样：
class Solution:
def subarraySum(self, nums: 'List[int]', k: int) -> int:
sums = 0
count = 0
dic = dict()
for n in nums:
if sums in dic.keys():
dic[sums] += 1
else:
dic[sums] = 1
sums += n
dif = sums - k
if dif in dic.keys():
count += dic[dif]
return count
下面进行解释，字典dic中存储的是某一个连续和的出现频率。例如nums=[1,1,1]，k=2。
第一次循环时，sums等于第零项的值0，则有{0:1}，表示连续和为0的情况出现了1次。
第二次循环时，sums等于第一项的值1，则有{0:1,1:1}，表示连续和为1出现了1次。
第三次循环时，sums等于前两项的值2，则有{0:1,1:1,2:1}，表示连续和为2出现了1次。
第四次循环时，sums等于前三项的值3，则有{0:1,1:1,2:1,3:1}，表示连续和为3出现了1次。
每一次循环的过程中都判断sums-k是否在字典dic中出现过，
如果出现过，则表示到当前位置的前x项中，包含有连续和为k的子集。
这一点是数学的技巧，也是提高效率的关键。