【大战蓝桥杯】 算法·每日一题（详解+多解）-- day9
【大战蓝桥杯】 算法·每日一题（详解+多解）-- day9
苏州程序大白
发布于 2022-05-10 18:33:01
发布于 2022-05-10 18:33:01
文章被收录于专栏：用户8907256的专栏
【大战蓝桥杯】 算法·每日一题（详解+多解）-- day9
✨博主介绍
🌊 作者主页：苏州程序大白 🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创始之一，目前合作公司富士康、歌尔等几家新能源公司
和为 k 的子数组
给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
示例 1： 输入:nums = [1,1,1], k = 2 输出: 2 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
示例 2： 输入:nums = [1,2,3], k = 3 输出: 2
提示:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107解题思路
题目要求的是 “连续子数组”, 因此此题和排序没关系；题目还要求的是子数组的个数。
数组有两个属性, 左边界和右边界, 我们设其分别为 i, j(j >= i)
假设nums[i] ~ nums[j]的子数组满足条件: 和为 k
设前缀和 sum[i] 表示nums[0] ~ nums[i]的和, 上述条件可以表述为
class Solution {
public int subarraySum(int[] nums, int k) {
int res = 0;
int sum = 0;
Map<Integer, Integer> sums = new HashMap<>(nums.length);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
// 查找前缀和中是否存在一个 target, 使得 sum - target = k
if (sum == k) {
++res;
}
int target = sum - k;
Integer count = sums.get(target);
if (count != null) {
res += count;
}
// 增加前缀和为 sum 的个数
sums.merge(sum, 1, Integer::sum);
}
return res;
}
}前缀和
- 根据题目描述可知数组中既有正数又有负数，无法使用双指针
- 后面再补充为什么有负数就不能使用双指针
- 所以利用前缀和思想
- 举例：
num如下，假设key为7。
值 | 1 | 2 | 3 | 4 | 5 | -5 | -3 | -1 | -4 | -5 |
|---|---|---|---|---|---|---|---|---|---|---|
前i项和 | 1 | 3 | 6 | 10 | 15 | 10 | 7 | 6 | 2 | -3 |
上表为从i=0一直到最后的值，需要寻找的就是某个sum[i]-k=sum[j]，那么此时i~j的范围就满足sum=k。
上表中i=3和i=5都满足，所以[3,4]和[3,4,5,-5]满足sum=k
-
map中的key和value分别为，前i项的和key，已经keyt出现的频次value-
map.put(0, 1)初始是和为0 - 时间复杂度O(N)，空间复杂度O(N)
-
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int res = 0, sum = 0;
map.put(0, 1);
for (int num : nums) {
sum += num;
if (map.containsKey(sum-k)) res += map.get(sum-k);
if (map.containsKey(sum)) map.put(sum, map.get(sum)+1);
else map.put(sum, 1);
}
return res;
}
}
//与上面一样，不过可能更优雅
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int res = 0, sum = 0;
map.put(0, 1);
for (int num : nums) {
sum += num;
res += map.getOrDefault(sum - k, 0);
map.merge(sum, 1, Integer::sum);
}
return res;
}
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-05-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
