当前位置 博文首页 > java牛牛的博客：[leetcode]560. 和为K的子数组
中等前缀和 哈希表前缀和 哈希表给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
题目理解：
nums 中找到连续子数组和为 k，并返回子数组个数preSum[0]preSum[0]...preSum[i+1]前缀和推倒过程：
preSum[0] = 0
preSum[1] = num[0] = preSum[0] + nums[0]
preSum[2] = num[0] + num[1] = preSum[1] + nums[1]
preSum[3] = num[0] + num[1] + nums[2] = preSum[2] + nums[2]
.
.
preSum[i+1] = num[0] + num[1] ... + nums[i] = preSum[i] + nums[i]
n ，遍历两次 ；n，其中 preSum[0] 为前缀初始值。class Solution {
public int subarraySum(int[] nums, int k) {
int len = nums.length;
// 计算前缀和数组
int[] preSum = new int[len + 1];
preSum[0] = 0;
for (int i = 0; i < len; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
int count = 0;
for (int left = 0; left < len; left++) {
for (int right = left; right < len; right++) {
// 区间和 [left..right]，注意下标偏移
if (preSum[right + 1] - preSum[left] == k) {
count++;
}
}
}
return count;
}
}
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
nums_len = len(nums)
pre_sum = [0] * (nums_len+1)
count = 0
for i,num in enumerate(nums):
pre_sum[i+1] = pre_sum[i] + num
for left in range(len(nums)):
for right in range(left,len(nums)):
if pre_sum[right+1] - pre_sum[left] == k:
count += 1
return count
map 中， map.put(preSum,前缀和出现次数) (数组中可能会有负数，所以可能会重复出现)public int subarraySum(int[] nums, int k) {
int count = 0;
// key:前i个元素的和，value：对应key 出现的个数
Map<Integer,Integer> preSumMap = new HashMap<>();
// 数组下标为 0，则前面数组为空，所以和为 0，且出现一次
preSumMap.put(0, 1);
int preSum = 0;
for(int i = 0;i<nums.length;i++) {
preSum += nums[i];
if (preSumMap.containsKey(preSum-k)){
count += preSumMap.get(preSum-k);
}
preSumMap.put(preSum, preSumMap.getOrDefault(nums[i], 0)+1);
}
return count;
}
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
pre_sum = 0
count = 0
pre_sum_dict = collections.defaultdict(int)
pre_sum_dict[0] = 1
for num in nums:
pre_sum += num
if pre_sum - k in pre_sum_dict:
count += pre_sum_dict.get(pre_sum - k)
pre_sum_dict[pre_sum] += 1
return count
复杂度分析：
n ，我们遍历数组长度为 nn，哈希表在最坏的情况下，保存 n 个不同元素如果你觉得本文对你有帮助，请点赞👍支持
如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出
