560. 和为 K 的子数组
题目描述
输入整数数组 nums 和整数 k。
子数组指数组中一段连续且非空的元素。统计所有元素之和恰好等于 k 的子数组有多少个，并返回这个数量。
起止位置不同的子数组分别计数，即使它们的元素内容一样。数组中可能有负数和 0。
示例 1
输入：nums = [1,1,1], k = 2 输出：2
解释：下标 [0,1] 和 [1,2] 两段的和都是 2。
示例 2
输入：nums = [1,2,3], k = 3 输出：2
解释：[1,2] 和 [3] 两段的和都是 3。
数据范围
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
解题思路：前缀和 + 哈希表
令 prefix 为当前位置前缀和。若此前出现过 prefix-k，说明对应前缀到当前位置的和为 k；用频次表累计。
为什么正确
处理当前位置前，freq[x] 是前面所有前缀和 x 的出现次数。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
只保存前缀和是否出现会漏算重复前缀，必须保存频次。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def subarraySum(self, nums,k):
freq={0:1}; prefix=ans=0
for x in nums:
prefix += x
ans += freq.get(prefix-k,0)
freq[prefix]=freq.get(prefix,0)+1
return ansclass Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
freq.put(0, 1);
int prefix = 0, ans = 0;
for (int x : nums) {
prefix += x;
ans += freq.getOrDefault(prefix - k, 0);
freq.put(prefix, freq.getOrDefault(prefix, 0) + 1);
}
return ans;
}
}class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> freq{{0, 1}};
int prefix = 0, ans = 0;
for (int x : nums) {
prefix += x;
ans += freq.count(prefix - k) ? freq[prefix - k] : 0;
freq[prefix]++;
}
return ans;
}
};func subarraySum(nums []int, k int) int {
freq := map[int]int{0: 1}
prefix, ans := 0, 0
for _, x := range nums {
prefix += x
ans += freq[prefix-k]
freq[prefix]++
}
return ans
}var subarraySum = function(nums, k) {
const freq = new Map([[0, 1]]);
let prefix = 0, ans = 0;
for (const x of nums) {
prefix += x;
ans += freq.get(prefix - k) || 0;
freq.set(prefix, (freq.get(prefix) || 0) + 1);
}
return ans;
};function subarraySum(nums: number[], k: number): number {
const freq = new Map<number, number>([[0, 1]]);
let prefix = 0, ans = 0;
for (const x of nums) {
prefix += x;
ans += freq.get(prefix - k) || 0;
freq.set(prefix, (freq.get(prefix) || 0) + 1);
}
return ans;
};其他解法
枚举法对每个终点重新遍历所有起点；前缀和 + 哈希表把“存在多少个起点”变成一次查表，用 O(n) 空间换到 O(n) 时间。
解法 2：枚举子数组起点 时间 O(n²)，空间 O(1)
枚举子数组的起点 i。从 i 向右扩展终点 j，边扩展边累加元素和。每次和等于 k 就计数加一。
不占额外空间，思路最直接。n 达到 2×10⁴ 时要约 2×10⁸ 次加法，比前缀和慢很多。数组有负数，所以不能用滑动窗口剪枝。
class Solution:
def subarraySum(self, nums, k):
n = len(nums)
ans = 0
for i in range(n):
s = 0
for j in range(i, n):
s += nums[j]
if s == k:
ans += 1
return ansclass Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length, ans = 0;
for (int i = 0; i < n; i++) {
int s = 0;
for (int j = i; j < n; j++) {
s += nums[j];
if (s == k) ans++;
}
}
return ans;
}
}class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size(), ans = 0;
for (int i = 0; i < n; i++) {
int s = 0;
for (int j = i; j < n; j++) {
s += nums[j];
if (s == k) ans++;
}
}
return ans;
}
};func subarraySum(nums []int, k int) int {
n, ans := len(nums), 0
for i := 0; i < n; i++ {
s := 0
for j := i; j < n; j++ {
s += nums[j]
if s == k {
ans++
}
}
}
return ans
}var subarraySum = function(nums, k) {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; i++) {
let s = 0;
for (let j = i; j < n; j++) {
s += nums[j];
if (s === k) ans++;
}
}
return ans;
};function subarraySum(nums: number[], k: number): number {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; i++) {
let s = 0;
for (let j = i; j < n; j++) {
s += nums[j];
if (s === k) ans++;
}
}
return ans;
}