560.M 和为 K 的子数组

Problem: 560. 和为 K 的子数组

思路

思路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：

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：

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
}