Lc0560

05 August 2008

560 - Subarray Sum Equals K

原题概述

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

1
2

Input:nums = [1,1,1], k = 2
Output: 2

Note:

  1. The length of the array is in range [1, 20,000].
  2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

题意和分析

1) 这道题是找到所有的子序列的个数，这些子序列的元素的和等于给定的一个target。暴力解法子数组左右两个边界遍历O(n^2)，嵌套加上求子数组的和O(n)，总共O(n^3)，不行。

2) 如果使用前缀和，可以先计算所有前缀的sum，可以降到两层循环，前缀和就是相当于固定了左边界，枚举右边界，或者固定右边界，枚举左边界，降了一维，O(n^2)。

3) 前缀和+哈希表优化做法：题目只关心子数组的个数，不关心具体的子数组长什么样子。定义preSum[i]为[0, i]之间元素的和，preSum[i]可以由preSum[i - 1]得到，即，preSum[i] = preSum[i - 1] + nums[i]：

preSum[i] - preSum[j] = nums[j + 1] + nums[j + 2] + …+ nums[i - 1] + nums[i] ?= k，简单移项转换成：

preSum[j] == preSum[i] - k

所以，统计有多少个preSum[i] - k等于preSum[j]这个条件的个数是我们需要的，于是把preSum[i] - k作为key，把前面计算的preSum[j]前面本身出现的次数作为value，如果再次出现(preSum[j] == preSum[i] - k)，说明等式成立，[i, j]这个区间出现了和为k的子数组，结果+1。

对于一开始的情况，下标 0 之前没有元素，可以认为前缀和为 0，个数为 1 个，因此 
1

preSumFreq.put(0, 1);
，这一点是必要且合理的。举例说明：

Array = {3,4,7,2,-3,1,4,2}，k= 7，如果遇到二者相减（sum - k）等于7，或者sum本身等于7或者7的倍数，subarray的count均+1，（注意黑体字）

如此，通过preSum[j] - preSum[i] = k的数目，计算出结果。Time：O(n)；Space：O(n)。

代码

只用前缀和，O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int result = 0;
        for (int right = 0; right < len; right++) {
            int preSum = 0; // 每次遍历每个sum记录以固定右边界的前缀和
            for (int left = right; left >= 0; left--) {
                preSum += nums[left];
                if (preSum == k) {
                    result++;
                }
            }
        }
        return result;
    }
}

前缀和 + HashMap优化，O(n)的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int preSum = 0;
        int result = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 初始化，表示达到target-t时的sum有一个
        
        for (int num : nums) {
            preSum += num;
            if (map.containsKey(preSum - k)) { // preSum[i] - preSum[j] = k移项
                result += map.get(preSum - k);
            }
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return result;
    }
}