Q560 和为 K 的子数组

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

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> valToCount; // 前缀和 → 出现次数
        valToCount[0] = 1;                  // 边界初始化
        int sum = 0, res = 0;

        for (int num : nums) {
            sum += num;                     // 累加当前前缀和
            int need = sum - k;
            if (valToCount.find(need) != valToCount.end()) // 此处为满足需求
            {
                res += valToCount[need];
            }
            valToCount[sum]++;
        }
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    mp[0] = 1;
    int sum = 0, ans = 0;
    for (int x : nums) {
        sum += x;
        if (mp.count(sum - k)) ans += mp[sum - k];
        mp[sum]++;
    }
    return ans;
}