和为 K 的子数组

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

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

题解：

​ 最暴力的方法是二次遍历计算从 i 到 j 的和，当然这里很容易想到使用前缀和，但是如果仅仅使用前缀和，我们依然需要使用 n方的时间复杂度来依次相减得到计数，这时候我们可以使用哈希表来降一重时间复杂度

​ （如果是计算非连续的子数组呢？可以使用递归或者回溯的方法或者动态规划）

func subarraySum(nums []int, k int) int {ans, pre := 0, 0sumMap := make(map[int]int)sumMap[0]++for i := 0; i < len(nums); i++ {pre += nums[i]if sumMap[pre-k] > 0 {ans += sumMap[pre-k]}sumMap[pre]++}return ans
}

func Backtrack(nums []int, k int) int {var dfs func(index, target int) intdfs = func(index, target int) int {if target == 0 {return 1}if index == len(nums) || target < 0 {return 0}// 不选当前元素 + 选当前元素return dfs(index+1, target) + dfs(index+1, target-nums[index])}return dfs(0, k)
}

func countSubsequences(nums []int, k int) int {n := len(nums)// dp[i][j] 表示从前 i 个元素中选取，和为 j 的方案数dp := make([][]int, n+1)for i := range dp {dp[i] = make([]int, k+1)}// 初始化：和为 0 的方案数为 1dp[0][0] = 1for i := 1; i <= n; i++ {for j := 0; j <= k; j++ {dp[i][j] = dp[i-1][j] // 不选当前元素if j >= nums[i-1] {dp[i][j] += dp[i-1][j-nums[i-1]] // 选当前元素}}}return dp[n][k]
}