Algorithm -- Classic Algorithm: Subarray Sum Equals K

🌐 中文

English

This article aims to explain how to implement the underlying logic of the classic algorithm for subarray sum equals k. Problem link: https://leetcode.cn/problems/subarray-sum-equals-k/

Introduction

Subarray sum equals k is a classic problem. Its optimal solution is O(n), achieved using prefix sums + a hash table.

Implementation Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<unordered_map>
class Solution {
public:
    unordered_map<int, int> map;   // value in nums array, index in nums
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0;
        int sum = 0;
        map[0] = 1;   // Initialize the count of prefix sum 0 as 1
        for(int i = 0; i < n; ++i){
            sum += nums[i];
            if(map.count(sum - k) > 0){
                ans += map[sum - k];
            }
            map[sum]++;
        }
        return ans;
    }
};

Logic Explanation

1. Use a hash table map to store the frequency of prefix sums. Initialize with map[0] = 1, indicating that a prefix sum of 0 has occurred once (i.e., before adding any numbers).
2. Because the sum value is recorded via the map, it has a forward-propagating property, allowing the optimization of vector<int> sums to a single sum variable, reducing space complexity.
3. Use the hashmap to record the frequency of sum values. When sum - k appears in the hashmap, it indicates the existence of a previous subarray whose sum equals k.
4. While traversing the array, calculate the current prefix sum sum each time, and check if sum - k exists in map. If it does, it means there is a subarray whose sum equals k. Add the corresponding count to the answer, and record the current prefix sum sum in map.

FAQ

Why does the same optimal solution code not outperform 100% of users?

When LeetCode’s backend executes your code, it may be assigned to different machines/containers. Factors like CPU load, cache, and memory usage can vary between machines, causing significant fluctuations in runtime for the same code across different submissions. This is why you might see large percentage variations (e.g., 92% → 99% → 84%) upon multiple submissions.

Summary

Using the prefix sum + hash table method, the subarray sum equals k problem can be solved in O(n) time complexity. This approach leverages the properties of prefix sums and the fast lookup capability of hash tables, making it a classic technique for solving such problems.