Loading... # 前缀和 LeetCode 560.和为K的子数组 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的 *个数* 。 示例 1： ``` 输入：nums = [1,1,1], k = 2 输出：2 ``` 示例 2： ``` 输入：nums = [1,2,3], k = 3 输出：2 ``` 提示： - `1 <= nums.length <= 2 * 104` - `-1000 <= nums[i] <= 1000` - `-107 <= k <= 107` ## 前缀和  ```java public int subarraySum(int[] nums, int k) { int count = 0; int len = nums.length; int[] preSum = new int[len + 1]; for (int i = 0; i < len; i++) { preSum[i + 1] = preSum[i] + nums[i]; } for (int i = 0; i < len; i++) { for (int j = i; j < len; j++) { if (preSum[j + 1] - preSum[i] == k) { count++; } } } return count; } ``` ## Hash表优化  ```java public int subarraySum(int[] nums, int k) { int count = 0; int preSum = 0; Map<Integer, Integer> preSumFreq = new HashMap<>(); preSumFreq.put(0, 1); for (int num : nums) { // preSum[i + 1] = preSum[i] + nums[i]; preSum += num; // 使用哈希表 省去内层 j 的循环 复杂度降到O(n) // for (int j = i; j < len; j++) { // preSum[j + 1] - k == preSum[i] count += preSumFreq.getOrDefault(preSum - k, 0); // preSum[i + 1] = preSum[i] + nums[i]; preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1); } return count; } ``` 最后修改：2023 年 02 月 02 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 本作品采用 CC BY-NC-SA 4.0 International License 进行许可。
