class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
}
};
剑指 Offer II 010. 和为 k 的子数组
给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
示例 1：
输入:nums = [1,1,1], k = 2 输出: 2 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
示例 2：
输入:nums = [1,2,3], k = 3 输出: 2
提示:
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
注意：本题与主站 560 题相同： https://leetcode.cn/problems/subarray-sum-equals-k/
原站题解
python3 解法, 执行用时: 80 ms, 内存消耗: 17.4 MB, 提交时间: 2022-11-23 16:08:26
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count, pre = 0, 0
m = defaultdict(int)
m[0] = 1
for i in range(len(nums)):
pre += nums[i]
if pre - k in m:
count += m[pre - k]
m[pre] += 1
return count
golang 解法, 执行用时: 40 ms, 内存消耗: 7.5 MB, 提交时间: 2022-11-23 16:03:45
// 前缀和 + 哈希表优化
func subarraySum(nums []int, k int) int {
count, pre := 0, 0
m := map[int]int{}
m[0] = 1
for i := 0; i < len(nums); i++ {
pre += nums[i]
if _, ok := m[pre - k]; ok {
count += m[pre - k]
}
m[pre] += 1
}
return count
}
golang 解法, 执行用时: 1136 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-23 16:02:45
func subarraySum(nums []int, k int) int {
count := 0
for start := 0; start < len(nums); start++ {
sum := 0
for end := start; end >= 0; end-- {
sum += nums[end]
if sum == k {
count++
}
}
}
return count
}