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的子集。

这一点是数学的技巧,也是提高效率的关键。

04-18 04:11