在一个数组中，找到和为K的连续子数组的个数。
可以很自然的想到枚举所有子数组组合。复杂度为n^2
public int subarraySum(int[] nums, int k) { int len = nums.length; int ans=0; for(int i=0;i<len;i++){ int sum=0; for(int j=i;j<len;j++){ sum+=nums[j]; if(sum==k) ans++; } } return ans; }
可以利用前缀和优化计算。preSum(i)为前i个数的和。sum(i,j)==k ====> preSum(j)-preSum(i-1)==k
我们简单的移项可以得到 preSum(j)-k == preSum(i-1)
我们利用哈希表存储preSum的值和它的个数。 统计 PreSum(j)-k 存在的总个数就可以了。
要注意的是，PreSum=0，天生就存个1个。
public int subarraySum2(int[] nums, int k) { int len = nums.length; HashMap<Integer,Integer> preSum = new HashMap<>(); int pre = 0; int ans = 0; for(int i=0;i<len;i++){ pre = pre + nums[i]; if(preSum.containsKey(pre-k)){ ans += preSum.get(pre-k); } preSum.put(pre,preSum.getOrDefault(pre,0)+1); } return ans; }
原文：https://www.cnblogs.com/superxuezhazha/p/12896134.html
