LeetCode Hot 100 P560 Subarray Sum Equals K

---

Timeline

Timeline

2026-03-11

init

Prefix sum

---

Problem:

P560 sum equals K subarray

https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked

prefix sum - a previous prefix sum = the sum of this interval

Enumeration:

#include <vector>
using std::vector;

class Solution {
    public:
        int subarraySum(vector<int> &nums, int k)
        {
                int i, j, n = nums.size();
                int cnt = 0;

                if (n == 0)
                        return 0;

                vector<int> prefix_sum(n + 1);

                // Compute prefix sums
                prefix_sum[0] = 0;
                for (i = 1; i <= n; i++)
                        prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1];

                // prefix[j] - prefix[i] == nums.sum(i..j)
                for (i = 0; i <= n; i++) {
                        for (j = i + 1; j <= n; j++)
                                if (prefix_sum[j] - prefix_sum[i] == k)
                                        cnt++;
                }

                return cnt;
        }
};

Hash table:

As long as umap[r+1] - k has appeared before, it means there exists a subarray with sum k.

#include <vector>
#include <unordered_map>

using std::unordered_map;
using std::vector;

class Solution {
    public:
        int subarraySum(vector<int> &nums, int k)
        {
                int res = 0;
                unordered_map<int, int> umap;
                vector<int> prefix_sum(nums.size() + 1, 0);

                umap[0] = 1;

                for (int i = 1; i < prefix_sum.size(); ++i) {
                        prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1];

                        // When k=0, inserting into umap will count itself.
                        res += umap[prefix_sum[i] - k]; // There may be multiple; only historical prefix sums can be counted, and the current preSum[i] cannot be included.

                        umap[prefix_sum[i]] += 1;
                                                
                }

                return res;
        }
};