子串：和为K的子数组

题目描述：给定一个整型数组和一个k，返回和为K的子数组(连续非空)的个数。

示例 1：

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

示例 2：

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

---

求解思路1：枚举法

枚举所有子串，在找所有子串的过程中统计和为k的子串个数。

时间复杂度：O(n^2)

空间复杂度：O(1)

class Solution {public int subarraySum(int[] nums, int k) {int result = 0;// 子数组[left.....right]for (int left = 0; left < nums.length; left++) {int sum = 0;for (int right = left; right >= 0; right--) {sum += nums[right];if (sum == k) {result++;}}}return result;}
}

---

求解思路2：前缀和+哈希。分析如下：

假设，数组nums为：[4,1,5,2]

则前缀和preSum为：[4,5,10,12]

preSum[0]=nums[0]

preSum[1]=preSum[0]+nums[1]

preSum[2]=preSum[1]+nums[2]

preSum[3]=preSum[2]+nums[3]

有了前缀和，又因为k为某个子数组的和，那么我们可以得出下图结果：

所以题目就可以转换为：求解有几个preSum[j]。

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {public int subarraySum(int[] nums, int k) {int result = 0;int preSum = 0;// preSumAndCountMap维护前缀和和前缀和出现的次数HashMap<Integer, Integer> preSumAndCountMap = new HashMap<>();// 初始化前缀和为0的次数为1preSumAndCountMap.put(0, 1);for (int i = 0; i < nums.length; i++) {preSum = preSum + nums[i];// 寻找一下是否有符合条件的if (preSumAndCountMap.containsKey(preSum - k)) {result = result + preSumAndCountMap.get(preSum - k);}// map表里记录一下int count = preSumAndCountMap.getOrDefault(preSum, 0);preSumAndCountMap.put(preSum, count + 1);}return result;}
}

练习地址：560. 和为 K 的子数组 - 力扣（LeetCode）