# 560.M 和为 K 的子数组

> Problem: [560. 和为 K 的子数组](https://leetcode.cn/problems/subarray-sum-equals-k/description/)

## 思路

思路1：前缀和。通过数组`sums`存储前缀和，`sum[i]`表示从`0`到`i`的和，然后有`[i..j]`序列的和为`sum[j] - sum[i-1]`。通过两层遍历，可以枚举出所有子序列的和。这种方式的时间复杂度为O($N^2$)

思路2：前缀和+哈希表。在思路1的基础上，把前缀和及其对应的个数存到map。然后遍历每个元素`nums[i]`在哈希表中寻找`sum[i]-k`的个数，能找到几个，则说明有几个以`i`为结尾元素的子序列有几个。

## Code

代码1：

```go
func subarraySumV1(nums []int, k int) int {
	sums := make([]int, len(nums))
	sums[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		sums[i] = sums[i-1] + nums[i]
	}

	ans := 0
	for i := 0; i < len(nums); i++ {
		for j := i; j < len(nums); j++ {
			if i == 0 && sums[j] == k {
				ans++
			}
			if i > 0 && sums[j]-sums[i-1] == k {
				ans++
			}
		}
	}

	return ans
}
```

代码2：

```go
func subarraySum(nums []int, k int) int {
	m := make(map[int]int)
	pre := 0
	ans := 0
	m[0] = 1
	for _, num := range nums {
		pre += num
		ans += m[pre-k]
		m[pre] += 1
	}

	return ans
}
```