class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
}
};
560. 和为 K 的子数组
给你一个整数数组 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原站题解
python3 解法, 执行用时: 92 ms, 内存消耗: 17.4 MB, 提交时间: 2022-11-23 16:08:14
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 解法, 执行用时: 44 ms, 内存消耗: 7.9 MB, 提交时间: 2022-11-23 16:03:50
// 前缀和 + 哈希表优化
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 解法, 执行用时: 1212 ms, 内存消耗: 6.6 MB, 提交时间: 2022-11-23 16:02:54
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
}