LeetCode 560. 和为 K 的子数组

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 560. 和为 K 的子数组

思路分析

前缀和+哈希表

参考代码

func subarraySum(nums []int, k int) int {
	hashtable := make(map[int]int)
	hashtable[0] = 1
	res, total := 0, 0
	for _, num := range nums {
		total += num
		if count, ok := hashtable[total-k]; ok {
			res += count
		}
		hashtable[total]++
	}
	return res
}

func subarraySum(nums []int, k int) int {
	count := 0
	sum := 0
	prefixSumCount := make(map[int]int)
	prefixSumCount[0] = 1 // 初始值，表示前缀和为 0 的情况

	for _, num := range nums {
		sum += num
		// 查找是否有前缀和为 sum - k
		if _, ok := prefixSumCount[sum-k]; ok {
			count += prefixSumCount[sum-k]
		}

		// 更新前缀和的出现次数
		prefixSumCount[sum]++
	}

	return count
}

时间复杂度：O(n)，其中 n 是数组的长度。

空间复杂度：O(n)，用于存储前缀和的哈希表。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/13096231