LeetCode刷题-top100（和为 K 的子数组）

560. 和为 K 的子数组

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

子数组是数组中元素的连续非空序列。

示例 1：

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

输出：2

示例 2：

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

输出：2

代码：双指针+两次循环，没有超时，差点

class Solution {public int subarraySum(int[] nums, int k) {int n = nums.length;int count = 0;for (int left = 0; left < n; left++) {int sum = 0;for (int right = left; right < n; right++) {sum += nums[right];if (sum == k) {count++;}// 如果数组包含负数，不能提前break// 因为后续可能有负数抵消前面的正数}}return count;}
}

最优解：哈希表+前缀和（前缀和总和是连续的所以存在pre-k，就一定有对应的连续数组）

import java.util.HashMap;
import java.util.Map;class Solution {public int subarraySum(int[] nums, int k) {// 哈希表：key-前缀和，value-该前缀和出现的次数Map<Integer, Integer> prefixSum = new HashMap<>();// 初始化：前缀和为0出现1次（用于处理从数组开头开始的子数组）// 例如：当sum == k时，sum - k = 0需要能被找到prefixSum.put(0, 1); //put不是pushint sum = 0;    // 当前前缀和（从第0个元素到当前元素的累加和）int count = 0;   // 统计满足条件的子数组数量for (int num : nums) {// 1. 计算当前前缀和sum += num;// 2. 检查是否存在前缀和等于(sum - k)// 如果存在，说明从该前缀和的位置到当前位置的子数组和为k// sum[0...j] - sum[0...i] = sum[i+1...j] = kif (prefixSum.containsKey(sum - k)) {// 累加该前缀和出现的次数（可能有多个位置满足）count += prefixSum.get(sum - k);}// 3. 更新当前前缀和的出现次数// 如果sum已存在，则次数+1；否则初始化为1prefixSum.put(sum, prefixSum.getOrDefault(sum, 0) + 1);}return count;}
}