LeetCode 560 和为 K 的子数组

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/subarray-sum-equals-k/description

博主Github：https://github.com/GDUT-Rp/LeetCode

题目：

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

示例 1:

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

示例 2:

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

提示：

• 1 <= nums.length <= $2\ast 10^4$
• 1000 <= nums[i] <= 1000
• $10^7$ <= k <= $10^7$

解题思路：

方法一：枚举

直接逐个枚举，就得到答案

Golang

func subarraySum(nums []int, k int) int {var ans intfor i:=0; i<len(nums); i++ {sum := nums[i]if sum == k {ans ++}for j:=i+1; j<len(nums); j++ {sum += nums[j]if sum == k {ans ++continue                }}}return ans
}

复杂度分析

时间复杂度：$O(n^2)$，其中 n 为数组的长度。枚举子数组开头和结尾需要 $O(n^2)$ 的时间，其中求和需要 O(1) 的时间复杂度，因此总时间复杂度为 $O(n^2)$。

空间复杂度：$O(1)$。

方法二：前缀和+map

遍历到每个值，可以统计出来前缀和，然后前缀和放到map去，例如k=7，m[7]=1, 到了m[14-7]的时候就可以有符合的条件。

Golang

func subarraySum(nums []int, k int) int {var (count intpre int)m := make(map[int]int)m[0] = 1for i := 0; i < len(nums); i++ {pre += nums[i]// pre[i] = pre[i-1] + nums[i]// pre[i] - pre[j-1] = k// pre[j-1] == pre[i] - kif v, ok := m[pre - k]; ok {count += v}m[pre] += 1}return count
}

复杂度分析

时间复杂度：$O(n)$。

空间复杂度：$O(n)$。