leetcode刷题（112）——560. 和为K的子数组
leetcode刷题（112）——560. 和为K的子数组
老马的编程之旅
发布于 2022-06-22 14:10:53
发布于 2022-06-22 14:10:53
文章被收录于专栏：深入理解Android
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
关键是，如何快速得到某个子数组的和呢，比如说给你一个数组nums，让你实现一个接口sum(i, j)，这个接口要返回nums[i…j]的和，而且会被多次调用，你怎么实现这个接口呢？
因为接口要被多次调用，显然不能每次都去遍历nums[i…j]，有没有一种快速的方法在 O(1) 时间内算出nums[i…j]呢？这就需要前缀和技巧了
前缀和的思路是这样的，对于一个给定的数组nums，我们额外开辟一个前缀和数组进行预处理：
int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
preSum[i + 1] = preSum[i] + nums[i];
在这里插入图片描述
这个前缀和数组preSum的含义也很好理解，preSum[i]就是nums[0…i-1]的和。那么如果我们想求nums[i…j]的和，只需要一步操作preSum[j+1]-preSum[i]即可，而不需要重新去遍历数组了。
回到这个子数组问题，我们想求有多少个子数组的和为 k，借助前缀和技巧很容易写出一个解法：
class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length;
int[] pre = new int[nums.length+1];
pre[0] = 0;
for(int i=1;i<=nums.length;i++){
pre[i] = pre[i-1]+nums[i-1];
}
int res = 0;
for(int i=1;i<=nums.length;i++){
for(int j=0;j<i;j++){
if (pre[i] - pre[j] == k)
res++;
}
}
return res;
}
}这个解法的时间复杂度图片空间复杂度图片，并不是最优的解法。不过通过这个解法理解了前缀和数组的工作原理之后，可以使用一些巧妙的办法把时间复杂度进一步降低。
前面的解法有嵌套的 for 循环：
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (sum[i] - sum[j] == k)
ans++;第二层 for 循环在干嘛呢？翻译一下就是，在计算，有几个j能够使得sum[i]和sum[j]的差为 k。毎找到一个这样的j，就把结果加一。
我们可以把 if 语句里的条件判断移项，这样写：
if (sum[j] == sum[i] - k)
ans++;优化的思路是：我直接记录下有几个sum[j]和sum[i]-k相等，直接更新结果，就避免了内层的 for 循环。我们可以用哈希表，在记录前缀和的同时记录该前缀和出现的次数。
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
HashMap < Integer, Integer > mp = new HashMap < > ();
mp.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (mp.containsKey(pre - k)) {
count += mp.get(pre - k);
}
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return count;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-02-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
