algorihtm--经典算法子数组累加和等于k

本文旨在讲解如何实现经典算法子数组累加和等于k的底层逻辑 本题连接: https://leetcode.cn/problems/subarray-sum-equals-k/

引言

子数组累加和等于k是一个经典的问题, 它的最优解为O(n), 最优解是使用前缀和 + 哈希表

具体实现代码

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;   // nums数组中的值, nums下标
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0;
        int sum = 0;
        map[0] = 1;   // 前面为0的值的个数初始化为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;
    }
};

逻辑解释

1. 使用一个哈希表 map 来存储前缀和出现的次数。初始化时，map[0] = 1，表示前缀和为0的情况出现了一次(也就是什么数都没有累加的时候)。
2. 因为其sum值通过map被记录, 具有向前推进的性质, 所以可以将vector sums优化为sum值, 优化空间复杂度
3. 使用hashmap记录sum值出现的次数, 当sum - k在hashmap中出现时, 说明存在一个前面的子数组的累加和为k
4. 遍历数组时, 每次计算当前的前缀和 sum，并检查 map 中是否存在 sum - k。如果存在，说明存在一个子数组的累加和为 k，将对应次数累加到答案中, 并记录当前的前缀和 sum 到 map 中。

FAQ

为什么和别人最优解代码相同却无法战胜100%的用户

LeetCode 后端执行你的代码时，会分配到不同的机器/容器。不同机器的 CPU 负载、缓存、内存占用情况都可能不同，导致同一份代码，不同时间跑出来的耗时差别很大。这就是为什么你多提交几次，可能百分比浮动很大（比如 92% → 99% → 84%）

总结

通过前缀和 + 哈希表的方法, 可以在O(n)的时间复杂度内解决子数组累加和等于k的问题, 这种方法利用了前缀和的性质以及哈希表的快速查找能力, 是解决此类问题的经典技巧

• Previous
  java25与其部分新特性