CS 知识库

简体中文

English

简体中文

English

主题

Subarray Sum Equals K ​

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

bash
Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

bash
Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

思路和算法 ​

我们可以基于方法一利用数据结构进行进一步的优化，我们知道方法一的瓶颈在于对每个 i，我们需要枚举所有的 j来判断是否符合条件，这一步是否可以优化呢？

我们定义 \(\textit{pre}[i]\)里所有数的和，则 \(\textit{pre}[i]\)可以由\(pre[i-1]\) 递推而来，即：

\(pre[i]=pre[i−1]+nums[i]\)

那么「\([j..i]\)这个子数组和为 \(k\)」这个条件我们可以转化为

\(pre[i]−pre[j−1]==k\)

简单移项可得符合条件的下标\(j\) 需要满足

\(pre[j−1]==pre[i]−k\)

所以我们考虑以 \(i\) 结尾的和为\(k\) 的连续子数组个数时只要统计有多少个前缀和为 \(\textit{pre}[i]-k\) 的 \(\textit{pre}[j]\)即可。我们建立哈希表 \(\textit{mp}\)，以和为键，出现次数为对应的值，记录 \(\textit{pre}[i]\)出现的次数，从左往右边更新 \(\textit{mp}\) 边计算答案，那么以 i 结尾的答案 \(\textit{mp}[\textit{pre}[i]-k]\)即可在 \(O(1)\) 时间内得到。最后的答案即为所有下标结尾的和为 \(k\) 的子数组个数之和。

需要注意的是，从左往右边更新边计算的时候已经保证了\(\textit{mp}[\textit{pre}[i]-k]\)里记录的\(\textit{pre}[j]\)的下标范围是\(0\leq j\leq i\)。同时，由于\(\textit{pre}[i]\)的计算只与前一项的答案有关，因此我们可以不用建立 \(\textit{pre}\) 数组，直接用 \(\textit{pre}\) 变量来记录 \(pre[i-1]\)的答案即可。

代码 ​

cpp
class Solution {
unordered_map<int,int> prefix;
public:
int subarraySum(vector<int>& nums, int k) {
    int preSum = 0;
    int total = 0;
    prefix[0] = 1;
    for(int i=0;i<nums.size();++i){
        preSum +=nums[i];
        if(prefix.count(preSum-k)){
            total+=prefix[preSum-k];
        }
        prefix[preSum]++;
    }
    return total;
}
};

523. Continuous Subarray Sum ​

Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.

A good subarray is a subarray where:

  • its length is at least two, and
  • the sum of the elements of the subarray is a multiple of k.

Note that:

  • A subarray is a contiguous part of the array.
  • An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Example 1:

bash
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Example 2:

bash
Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Example 3:

bash
Input: nums = [23,2,6,4,7], k = 13
Output: false

Constraints:

  • \(1 <= nums.length <= 10^5\)
  • \(0 <= nums[i] <= 10^9\)
  • \(0 <= sum(nums[i]) <= 2^{31} - 1\)
  • \(1 <= k <= 2^{31} - 1\)

思路 ​

与上题一样，本题要求的前缀和需要满足：pre[i]−pre[j−1]==n*k，即 \(k\mid (pre[i]-pre[j-1])\)，根据同余充要条件可知，即满足\(pre[i]\equiv pre[j-1](modm)\)。

所以我们的 hash map里面key就是余数即可！然后由于需要满足ts length is at least two，那么value就是下标，且是第一次为该余数的下标。

唯一需要注意的是，如果余数在其中算的时候如果第一次算出来为0了，表示整个数组从头到位就是k的整数倍，这个时候hash map里是没有值的！！！所以可以给一个虚拟的map[0] = -1表示可以返回答案。

cpp
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> presum;
        int remainder = 0;
        //如果中途算出来正好余数为0，表示整个前缀和可用。
        presum[remainder] = -1;
        for(int i=0;i<nums.size();i++){
            remainder = (remainder + nums[i]) % k;
            if(presum.count(remainder)&& i - presum[remainder]>=2){
                return true;
            }
            //放置最早的那一个下标，保证 at least two
            if(!presum.count(remainder)) presum[remainder] = i; 
        }
        return false;
    }
};

Path Sum III ​

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1:

bash
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

plain
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

Constraints:

  • The number of nodes in the tree is in the range [0, 1000].
  • -10^9 <= Node.val <= 10^9
  • -1000 <= targetSum <= 1000

前缀和定义 ​

一个节点的前缀和就是该节点到根之间的路径和。

拿下图解释：

  • 节点4的前缀和为：1 + 2 + 4 = 7
  • 节点8的前缀和：1 + 2 + 4 + 8 = 15
  • 节点9的前缀和：1 + 2 + 5 + 9 = 17
bash
      1
     /  \
    2    3
   / \    \
  4   5    6
 / \   \
7   8   9

前缀和对于本题的作用 ​

题目要求的是找出路径和等于给定数值的路径总数, 而:两节点间的路径和 = 两节点的前缀和之差

本题的一个优化切入点为「路径只能往下」，因此如果我们转换一下，统计以每个节点为「路径结尾」的合法数量的话，配合原本就是「从上往下」进行的数的遍历（最完整的路径必然是从原始根节点到当前节点的唯一路径），相当于只需要在完整路径中找到有多少个节点到当前节点的路径总和为 targetSum。

于是这个树上问题彻底转换一维问题：求解从原始起点（根节点）到当前节点 b 的路径中，有多少节点 a 满足 sum[a...b] = targetSum，由于从原始起点（根节点）到当前节点的路径唯一，因此这其实是一个「一维前缀和」问题。

具体的，我们可以在进行树的遍历时，记录下从原始根节点 root 到当前节点 cur 路径中，从 root 到任意中间节点 x 的路径总和，配合哈希表，快速找到满足以cur为「路径结尾」的、使得路径总和为 targetSum的目标「路径起点」有多少个。

还是拿下图解释：

bash
                     1
                    / 
                   2    
                  / 
                 3   
                / 
               4

假如题目给定数值为5

bash
节点1的前缀和为: 1
节点3的前缀和为: 1 + 2 + 3 = 6

prefix(3) - prefix(1) == 5
所以 节点1 到 节点3 之间有一条符合要求的路径( 2 --> 3 )

所以：我们只用遍历整颗树一次，记录每个节点的前缀和，并查询该节点的祖先节点中符合条件的个数，将这个数量加到最终结果上。

HashMap存的是什么 ​

HashMap的key是前缀和， value是该前缀和的节点数量，记录数量是因为有出现复数路径的可能。

下图树中，前缀和为1的节点有两个: 1, 0

所以路径和为2的路径数就有两条: 0 --> 2, 2

bash
      1
     / 
    0
   /
  2

恢复状态的意义 ​

由于题目要求：路径方向必须是向下的（只能从父节点到子节点）

当我们讨论两个节点的前缀和差值时，有一个前提：一个节点必须是另一个节点的祖先节点

换句话说，当我们把一个节点的前缀和信息更新到map里时，它应当只对其子节点们有效。

举个例子，下图中有两个值为2的节点（A, B)。

bash
      0
     /  \
    A:2  B:2
   / \    \
  4   5    6
 / \   \
7   8   9

当我们遍历到最右方的节点6时，对于它来说，此时的前缀和为2的节点只该有B, 因为从A向下到不了节点6(A并不是节点6的祖先节点)。

由于我们只能统计往下的路径，但是树的遍历会同时搜索两个方向的子树。因此我们应当在搜索完以某个节点为根的左右子树之后，应当回溯地将路径总和从哈希表中删除，防止统计到跨越两个方向的路径。

如果我们不做状态恢复，当遍历右子树时，左子树中A的信息仍会保留在map中，那此时节点6就会认为A, B都是可追溯到的节点，从而产生错误。

状态恢复代码的作用就是： 在遍历完一个节点的所有子节点后，将其从map中除去。比如A:2所有子树遍历完后删除，这样就重新定位到0-B:2这条路径了！

代码 ​

注意这里root->val最大为\(10^9\),最多有\(10^3\)个节点，所以前缀和最大为\(10^{12}\),需要40bit = 5byte，所以int会溢出，前缀和表至少需要long类型。

cpp
class Solution {
unordered_map<long long,int> prefix;
int prefixSum(TreeNode* root,int targetSum, long long curSum){
    if(!root) return 0;
    curSum +=root->val;
    int ret = 0;
    if(prefix.count(curSum - targetSum)>0){
        ret = prefix[curSum - targetSum];
    }
    prefix[curSum]++;
    int left = prefixSum(root->left,targetSum,curSum); 
    int right = prefixSum(root->right,targetSum,curSum);
    //搜索完后回溯地将路径总和从哈希表中删除
    prefix[curSum]--;
    //这里需要加上左右子树的结果总数，表示如果选择当前节点，并继续选左右子树节点后新增的路径数目
    return ret+left+right;
}
public:
int pathSum(TreeNode* root, int targetSum) {
    prefix[0] = 1;//base case，空路径前缀和为0.
    return prefixSum(root,targetSum,0);
}
};

用心记录，持续成长

Copyright © 2026 hswsp