LeetCode Daily Question 16

Mar 30th 2022

3 月 31 日 每日一题

题目：560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

1
2
3
4
5
6
7
8
Example 1:

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

Input: nums = [1,2,3], k = 3
Output: 2
1
2
3
4
5
Constraints:

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

思路

因为 constrain 提到 nums 中可能有负数，所以本题无法使用 sliding window（无法保证区间缩小会使 sum 减小）。正确做法是使用一个命名为 prefixNum 的 hashmap 存储每一个 prefixSum 出现的次数。并使用一个 for 循环从 0 - 0， 0 - 1， 0 - 2 逐渐扩大 subarray size，如果当前的 sum - k 的数字可以在 hashmap 中找到，说明当前范围，减去 prefix 的范围可以得到 k，那么此时 res + prefixSum 的 second value。
本题需要考虑三个点，第一个 edge case 是 prefixSum 为 0 例如 1 + 1 为 2， k 为 2，并不需要减去 prefix，所以在开始遍历之前要给 prefixSum = 0 赋 1.
第二，不能先记录 prefixSum 再开始遍历，这样可能会出现 window 比当前区间大的情况。
第三，循环时应该先判断 judge 再记录 prefixSum，以避免 window 是当前区间本身。

代码

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

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixSum;
        prefixSum[0] = 1;
        size_t size = nums.size();
        int sum = 0;
        int res = 0;
        for(int i = 0; i < size; i++){
            sum += nums[i];
            int judge = sum - k;
            auto iter = prefixSum.find(judge);
            if(iter != prefixSum.end()){
                res += iter->second;
            }
            prefixSum[sum]++;
        }
        return res;
    }
};

错误实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixSum;
        prefixSum[0] = 1;
        size_t size = nums.size();
        int res = 0;
        for(int i = 0; i < size; i++){
            int sum = 0;
            for(int j = i; j >= 0; j--){
                sum += nums[j];
            }
            int judge = sum - k;
            auto iter = prefixSum.find(judge);
            if(iter != prefixSum.end()){
                res += iter->second;
            }
            prefixSum[sum]++;
        }
        return res;
    }
};
, ,
  1. 3 月 31 日 每日一题
    1. 题目：560. Subarray Sum Equals K
    2. 思路
    3. 代码