leetcode 560.和为k的子数组
思路一:可以仿照数据结构黑皮书中第一章演示最大子段和的做法,我们可以暴力求解,然后在暴力做法的基础上,边计算边判断,降低时间复杂度至O(n2).
class Solution {public int subarraySum(int[] nums, int k) {int res=0;for(int i=0;i<nums.length;i++){int sum=0;for(int j=i;j<nums.length;j++){sum+=nums[j];if(sum==k){res++;}}}return res;}
}思路二:前缀和.对于子序列问题,一般来说就会用到滑动窗口的双指针,以及前缀和这种思想.这里也是,前缀和对于子序列求解的本质其实就是对于各个区间相加减得到全部子区间的过程.
class Solution {public int subarraySum(int[] nums, int k) {int[]qian=new int[nums.length+1];for(int i=1;i<=nums.length;i++){qian[i]=qian[i-1]+nums[i-1];}int count=0;for(int i=0;i<nums.length;i++){for(int j=i+1;j<=nums.length;j++){if(qian[j]-qian[i]==k)count++;}}return count;}
}思路三:前缀和+哈希表
实际上就是这个意思:a+b=c,那么我们可以推知c-b=a.这个道理用在哈希表查询上.
我们求出来前缀和之后,其实也就是变相知道了某个区间的和,就如上面所说的,如果两个区间相减为k,那么我们只需要求出该前缀和-k存不存在有那么一个区间是刚刚成立的那个式子的值.逆向思维.
哈希表的主要目的就是存储区间和的次数.
注意需要将0,1这一对先赋值进去.否则当数组中出现0元素的时候就不行了.
class Solution {public int subarraySum(int[] nums, int k) {int[]qian=new int[nums.length+1];for(int i=1;i<=nums.length;i++){qian[i]=qian[i-1]+nums[i-1];}int count=0;Map<Integer,Integer>map=new HashMap<>();map.put(0,1);for(int i=1;i<=nums.length;i++){int sum=qian[i];int t=sum-k;count+=map.getOrDefault(t,0);map.put(sum,map.getOrDefault(sum,0)+1);}return count;}
}