LeetCode560之和为K的子数组（相关话题：前缀和）

题目描述

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

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数?k?的范围是?[-1e7, 1e7]。

思路分析

这个前缀和数组preSum的含义也很好理解，preSum[i]就是nums[0..i-1]的和。那么如果我们想求nums[i..j]的和，只需要一步操作preSum[j+1]-preSum[i]即可，而不需要重新去遍历数组了。

int subarraySum(int[] nums, int k) {
    int n = nums.length;
    // 构造前缀和
    int[] sum = new int[n + 1];
    sum[0] = 0; 
    for (int i = 0; i < n; i++)
        sum[i + 1] = sum[i] + nums[i];

    int ans = 0;
    // 穷举所有子数组
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            // sum of nums[j..i-1]
            if (sum[i] - sum[j] == k)
                ans++;

    return ans;
}

这个解法的时间复杂度空间复杂度，并不是最优的解法。不过通过这个解法理解了前缀和数组的工作原理之后，可以使用一些巧妙的办法把时间复杂度进一步降低。

优化的思路是：我直接记录下有几个sum[j]和sum[i]-k相等，直接更新结果，就避免了内层的 for 循环。我们可以用哈希表，在记录前缀和的同时记录该前缀和出现的次数。

代码实现

    public int subarraySum(int[] nums, int k) {
        
        Map<Integer,Integer> map = new HashMap(); 
        int sum_i = 0;
        int sum_j = 0;
        int result = 0;
        map.put(0,1);
        for(int i=0;i<nums.length;i++){

            sum_i = sum_i + nums[i];
            //和当前前缀和sum_i差k的前缀和为sum_j
            sum_j = sum_i- k;
            if(map.get(sum_j)!=null){
                //之前存在这个前缀和就把结果加1
                result = result + map.get(sum_j);
            }
             map.put(sum_i,map.getOrDefault(sum_i,0)+1);

        }

      return result;

  }

?

?

?