题目描述
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
样例
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
算法1
(暴力枚举) $O(n^2)$
暴力枚举的想法就是以数组中每个值作为左边界,向右边遍历,在遍历的时候看看看看区间内的总和是否 == k。
时间复杂度
经历两次for 循环,并且两次for 循环的最大次数都是n,所以整体时间复杂度: O(n^2)
参考文献
Java 代码
public int subarraySum(int[] nums, int k) {
if(nums.length == 0) return nums.length;
int count = 0;
for(int left = 0; left < nums.length; left ++){
int sum = 0;
for(int right = left; right < nums.length; right ++){
sum += nums[right];
//因为要求是在连续的子数组中找到和为k 的个数
//所以答案必须是在数组是挨着的
if(sum == k){
count ++;
}
}
}
return count;
}
算法2
(前缀和) $O(n^2)$
这个主要是一个过渡思想,为的就是提炼出 “前缀和” 的思想,关于前缀和的概念:
前缀和:nums 的第 0 项到 当前项 的和。
用数组 prefixSum 表示,prefixSum[x]:第 0 项到 第 x 项 的和:prefixSum[x]=nums[0]+nums[1]+…+nums[x]
nums 的某项 = 两个相邻前缀和的差:nums[x]=prefixSum[x]−prefixSum[x−1]
nums 的 第 i 到 j 项 的和,有:nums[i]+…+nums[j]=prefixSum[j]−prefixSum[i−1]
当 i 为 0,此时 i-1 为 -1,我们故意让 prefixSum[-1] 为 0,使得通式在i=0时也成立:
nums[0]+…+nums[j]=prefixSum[j]
并且当i = 0 时, nums[0] = prefixSum[0] - prefixSum[-1] = 0; 因为数组最小索引是: 0 所以
我们就把这个最小索引变成0,此时 prefixSum[0] = 0,代表在nums[0] 前面的数的前缀和为0.
时间复杂度
O(n^2)
参考文献
Java 代码
public int subarraySum(int[] nums, int k) {
if(nums.length == 0) return nums.length;
int count = 0;
int[] preSum = new int[nums.length + 1];
preSum[0] = 0;
for(int i = 0; i < nums.length; i++){
preSum[i+1] = preSum[i] + nums[i];
}
for(int left = 0; left < nums.length; left++){
for(int right = left; right < nums.length; right++){
if(preSum[right + 1] - preSum[left] == k){
count ++;
}
}
}
return count;
}
算法2
(前缀和 + Map) $O(n^2)$
有了上面的前缀和的思想以后,我们做这题就不是关注在nums 数组中哪几个子数组的和为k了,而是关注nums 数组中存在前缀和 (prefixSum - k) 的个数有几个. 为什么要prefixSum - k? 首先我们要说Map 存的键值对是什么. map 的key 存的是当前num 的前缀和,value 对应该前缀和出现的次数。 那么如果后面的前缀和prefixSum 减去k 得到的数还能够在map 中找到对应的key, 说明这个key 是之前的num 的前缀和,也就说明[prefixSum - k , prefixSum] 这个连续子数组,它们的总和为k。接着我们就把这个区间出现的次数加入到count 中即可。
时间复杂度
O(n)
参考文献
Java 代码
public int subarraySum3(int[] nums, int k) {
if(nums.length == 0) return nums.length;
int count = 0;
Map<Integer,Integer> map = new HashMap<>();
//为什么是key = 0,value = 1
//一种特殊情况: nums[k,....] 当数组中第一个数,它的值就是k,那么根据我们的运算:preSum - k == 0
//这种情况是要考虑进去的
map.put(0,1);
int preSum = 0;
for(int num : nums){
preSum += num;
if(map.containsKey(preSum - k)){
count += map.get(preSum - k);
}
map.put(preSum,map.getOrDefault(preSum,0) + 1);
}
return count;
}