Subarray Sum Equals K trong C++

Cho mảng số nguyên và số k. Tìm số subarray liên tiếp có tổng bằng k.

Ví dụ: nums=[1,1,1], k=2 → output 2.

Giải thuật (Prefix Sum + HashMap)

• sums map lưu tần suất prefix sum. Khởi tạo sums[0]=1.
• temp=0, ans=0.
• Duyệt mảng:
  • temp += nums[i].
  • Nếu sums.count(k - temp) thì ans += sums[k-temp].
  • sums[temp]++.
• Trả về ans.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    Solution ob;
    vector<int> v = {1,1,1};
    cout << ob.subarraySum(v, 2);
    return 0;
}

Input

[1,1,1] 2

Output

2