题目链接

题目:

分析:

• 思考: 此题能否用滑动窗口来解决?
  滑动窗口的适用前提是具有单调性, left和right指针是不回退的, 此题中数组有负数和零, 很难保证指针不回退, 所以不能用滑动窗口
• 利用前缀和的思想, 计算以i结尾的所有子数组, 前缀和为sum[i] 
• 想要找到和为k的数组, 我们只需要找到在[0,i-1] 区间内, 有多少个前缀和等于sum[i] - k 
• 想要得到前缀和的个数, 我们需要用到hash表:<int,int>
• 细节:
  • 1. 前缀和加入哈希表的时机?
    因为要计算[0,i-1] 区间的前缀和, 所以要先更新前缀和为sum[i] - k 的个数, 再将sum[i]放到哈希表中
  • 2. 不用真的创建一个前缀和数组
    因为我们只需要记录和为k的个数, 不需要知道下标等其他信息, 所以我们用一个变量sum记录前缀和即可, sum每次更新
  • 3. 如果整个前缀和等于k?
    如果从0到i的位置的和是k, 那么在[0,i-1] 的位置寻找和为sum - k应该是0, 也是一种情况, 所以哈希表中应该添加(0,1)

代码:

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0,1);
        int sum = 0;//存储前缀和
        int ret = 0; //存储和为k的个数
        for(int i = 0;i<nums.length;i++){
            sum += nums[i];
            ret += hash.getOrDefault(sum - k,0);
            hash.put(sum,hash.getOrDefault(sum,0) + 1);
        }
        return ret;

    }
}