HHot 100C++ 图解

560. 和为 K 的子数组

中等 子串 / 前缀和 5 帧动画 在力扣上做

一句话套路前缀和 + 哈希计数(有负数不能用滑窗)

题目描述

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

 

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2

 

提示:

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107

思路

时间O(n)
空间O(n)

思路

遍历到 r 时,需要知道「之前有几个前缀和等于 cur - K」。

cnt[0] = 1 必须有 —— 它代表「从下标 0 开始就恰好等于 K」的那种子数组。

易错

nums 含负数,不能用滑动窗口(右扩不保证和变大)。

计数用 long long

n = 2×10^5 全为 0、k = 0 时答案是 n(n+1)/2 ≈ 2×10^10,用 int 累加会在返回前就溢出(签名是力扣固定的 int,至少保证中间过程正确)。

图解

3 0 4 1 7 2 2 3 -3 4 1 5 4 6 2 7
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 5

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/04_substring.cpp18 行
namespace lc0560 {
class Solution {
 public:
  int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;  // 前缀和 -> 出现次数
    cnt[0] = 1;
    int cur = 0;
    long long ans = 0;  // 见上方「易错」:答案本身可能超出 int
    for (int x : nums) {
      cur += x;
      auto it = cnt.find(cur - k);
      if (it != cnt.end()) ans += it->second;
      ++cnt[cur];  // 先查后存,保证子数组非空
    }
    return static_cast<int>(ans);
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q560_subarray_sum_equals_k13 行
lc0560::Solution s;
vector<int> a{1, 1, 1};
CHECK_EQ(s.subarraySum(a, 2), 2);
vector<int> b{1, 2, 3};
CHECK_EQ(s.subarraySum(b, 3), 2);  // [1,2] 和 [3]
vector<int> c{1, -1, 0};
CHECK_EQ(s.subarraySum(c, 0), 3);  // [1,-1] [1,-1,0] [0],含负数
vector<int> d{3, 4, 7, 2, -3, 1, 4, 2};
CHECK_EQ(s.subarraySum(d, 9), 1);  // 只有 [7,2]:-3 把后面的和拉低后不再凑效
vector<int> e{0, 0, 0};
CHECK_EQ(s.subarraySum(e, 0), 6);  // 全 0:所有子数组都合法,C(3+1,2)=6
vector<int> f{1, 2, 1, 2, 1};
CHECK_EQ(s.subarraySum(f, 3), 4);

↑↓ 选择↵ 打开/ 随时唤起