【大战蓝桥杯】 算法·每日一题（详解+多解）-- day9
✨博主介绍
和为 k 的子数组
解题思路
💫点击直接资料领取💫
✨博主介绍
🌊 作者主页：苏州程序大白
🌊 作者简介：🏆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; } }
