4.9 前缀和解决子数组问题

4.9.1 问题描述

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

暴力的思路是直接穷举所有的子数组然后求和即可，关键是如何快速地得到某个子数组的和?比如给你一个数组nums,让你实现一个sum(i,j)，该接口应该要返回nums[i...j]的和，而且会被多次调用，因为接口会被多次调用，显然不能每次都去遍历nums[i..j]，我们希望以O(1)的时间复杂度来完成这个事情

4.9.2 什么是前缀和

思路:对于一个给定的数组nums，额外开辟一个前缀和数组进行预处理

int n = nums.length;
//前缀和数组:定义前n项的和,也就是下标从[0...i-1]的和
int[] preSum = new int[n+1];//n+1:因为需要记录前n项的和,因此需要多一位
preSum[0] = 0 ;//前0项的和当然为0
for(int i = 1 ;i<=n;i++){
    preSum[i] = preSum[i-1] + nums[i-1];
}

如果想求nums[i...j]的和，只需要一步操作preSum[j+1] - preSum[i]即可
回到该问题上，如果想要求所有的子数组组合，那么最简单的办法就是使用双for循环来遍历数组即可，但是这样的时间复杂度是O(N^2)，理论上可以优化

4.9.3 优化解法

双for循环解法

for(int i = 1;i<= n;i++){
    for(int j=0;j<i;j++){
        if(sum[i] - sum[j] == k){
            ans++;
        }
    }
}

分析第二层for循环，其作用是在计算有几个j能够使得sum[i]和sum[j]的差为k(子数组之和)，每找到一个这样的j，就把结果+1，将条件判断语句移项:sum[j] == sum[i]-k
优化的思路是直接记录下有几个sum[j]和sum[i]-k相等，直接更新结果，就避免了内层的for循环，可以使用哈希表，在记录前缀的同时记录该前缀和出现的次数

public int subarraySum(int[] nums, int k) {
    int n = nums.length;
    //map:前缀和->该前缀和出现的次数
    Map<Integer,Integer> map = new HashMap<>();
    //base-case
    map.put(0,1);//前0项的和为0,而且出现了一次
    int ans = 0,sum0_i = 0;
    for(int i =0;i<n;i++){
        sum0_i += nums[i];
        //这是我们想找的前缀和nums[0....j]
        int sum0_j = sum0_i-k;
        //如果前面有这个前缀和,那么直接更新答案
        if(map.containsKey(sum0_j)){
            ans += map.get(sum0_j);
        }
        //把前缀和nums[0....i]加入并记录出现次数
        map.put(sum0_i,map.getOrDefault(sum0_i,0)+1);
    }
    return ans;
}