class Solution {
public int subarraySum(int[] nums, int k) {
int length=nums.length;
// key 表示前缀和,value 表示个数
HashMap<Integer,Integer> hashMap =new HashMap<Integer,Integer>();
//默认有一个前缀和为 0 的数据,解决下标前缀和直接为 0 的特殊情况
hashMap.put(0,1);
int last=0; //前一个下标的前缀和
int now=0; //当前下标的前缀和
int count=0; //记录符合条件的子数组个数
for(int i=0;i<length;i++){
now=last+nums[i];
int find=now-k; //计算要在哈希表中查找的前缀和
count+=hashMap.getOrDefault(find,0);
//将当前下标的前缀和添加到哈希表中
hashMap.put(now,hashMap.getOrDefault(now,0)+1);
last=now;
}
return count;
}
}
? ? ? ? 本题的题意很清晰,需要统计出该数组中和为?k
?的子数组的个数?
? ? ? ? 要注意题目给出的数据范围是?-1000 <= nums[i] <= 1000,
所以数组中存在小于等于 0 的数据
? ? ? ? 先来思考一下本题的暴力解法,我们将所有的子数组遍历出来,统计出其中和为?k
?的子数组的个数?即可,时间复杂度为 O(n^2),这是一个很大的时间复杂度,所以我们需要进行优化
? ? ? ? 本题可以用前缀和的方式来进行优化,定义一个前缀和数组 sum,sum[ i ] 代表从 0 ~ i 的数据总和,为了便于理解,我画了如下的图:
? ? ? ? 如上图,我们要统一以下标 i 为尾的符合条件的子数组个数,就需要在 0~ i -1 中找到下标 j ,使 j 到 i 之间数据和为 k,即我们要 0~ i -1 找到 j 下标使 sum[ j-1 ] = sum [ i ] - k ,找到多少个符合条件的 j 下标就代表以下标 i 为尾的符合条件的子数组个数有多少个,更简单来说就是,在 0~ i -1 中有多少个下标的前缀和 =?sum [ i ] - k ,就代表以下标 i 为尾的符合条件的子数组个数有多少个
? ? ? ? 我们可以将已经获取到的前缀和记录到哈希表中,前缀和为 key ,个数为 value,记录在 i 下标之前,各个前缀和对应的个数
? ? ? ? 以 nums = 1,2,3? k = 3 为例,i 一开始指向 0 下标,前缀和 sum[ 0 ] = 1,我们要查找的前缀和是? sum [ 0?] - k = 1 - 3 = -2,在哈希表中没有 -2 这个前缀和对应的数目,所以没有符合条件的子数组,i 向下遍历,将当前的前缀和记录到哈希表中
1????????2????????3????????????????? ? ? ? 哈希:
????????????????????????????????????????????????????????key = 1,value =1
i
????????前缀和 sum[ 1?] = 3,我们要查找的前缀和是? sum [ 1?] - k = 3 - 3 = 0,在哈希表中没有 0?这个前缀和对应的数目,但实际上现在 0~i 之间的子数组已经是满足要求的了,所以我们这里没有考虑到? sum [ i ] - k = 0 的特殊情况,所以一开始创建哈希表时就应该添加 key = 0,value =1(前缀和为 0 的下标有一个) 这个数据
? ? ? ? 此时在哈希表中就获取到了0?这个前缀和对应的数目 1 ,我们便得到以 1 下标为尾的符合条件的子数组个数为 1,将其记录到 count 中,将当前的前缀和记录到哈希表中
1????????2????????3? ? ? ? ????????????????哈希:
? ? ? ? ? i? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????key = 0,value =1
??????????????????????????????????????????????????????key = 1,value =1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????key = 3,value =1
? ? ? ? i 继续向下遍历,??前缀和 sum[ 2?] = 6,我们要查找的前缀和是? sum [ 2?] - k = 6?- 3 = 3,在哈希表中前缀和为 3 的下标有 1 个,所以便得到以 2 下标为尾的符合条件的子数组个数为 1,将其记录到 count 中,将当前的前缀和记录到哈希表中
1????????2????????3???????????????????????? ? ? ? 哈希:
? ? ? ? ? ? ? ? ? ? i? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??key = 0,value =1
???????????????????????????????????????????????????????key = 1,value =1
???????????????????????????????????????????????????????key = 3,value =1
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?key = 6,value =1
? ? ? ? 而要获取当前 i 下标的前缀和很容易,我们在获取 i 下标的前缀和就已经知道 i - 1 下标的前缀和了,所以 sum[ i ] = sum[ i-1 ] + nums[ i ] ,提前设置好 0 下标之前前缀和为 0 即可
? ? ? ? ??