剑指 Offer II 010. 和为 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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/QTMn0o
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路及方法
最初想的是滑动窗口、或者暴力,后面觉得前缀和貌似效率更高。
我们并不需要构建一个数组来记录前缀和,只用维护一个变量sum,遍历数组时对sum进行更新,同时用一个map记录sum出现的次数。类似于力扣第一题两数之和,我们每次遍历时,都判断map中是否存在sum-k,存在则说明上一次出现sum的下标到遍历本次时的连续子数组和为k,记录出现sum-k的次数即可。
class Solution {
public int subarraySum(int[] nums, int k) {
// 前缀和,map记录前i个数和以及出现次数
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int res = 0;
// 记录前缀和
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
// map存在sum - k,及说明存在i之前某一位置到i连续子数组和为k
if (map.containsKey(sum - k)) {
res += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return res;
}
}
结果如下:
剑指 Offer II 011. 0 和 1 个数相同的子数组
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。
示例 1:
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
提示:
1 <= nums.length <= 105
nums[i] 不是 0 就是 1
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/A1NYOS
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路及方法
和上一道题一样,也是前缀和+哈希表,注释已经写的很清楚了。这里说一下初始入map,没有元素时前缀和为0,但它的下边为-1,是为了后续计算子数组长度时用当前下标减去-1即可,就不用像计算普通长度时是j - i + 1。
用变量sum记录前缀和,遇见1加1,遇见0减1,这样保证下一次当前缀和为sum且map中存在sum时,构成的子数组经过+相同数量的1和-相同数量的1,则代表子数组中有相同数量的0和1,对比长度即可。
class Solution {
public int findMaxLength(int[] nums) {
int res = 0;
// 记录前缀和
int sum = 0;
// 记录前缀和及下标
Map<Integer, Integer> map = new HashMap<>();
// 记录初始前缀和
map.put(0, -1);
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
// 为1加1,为0减1
if (num == 1) sum++;
else sum--;
// 如果map包含sum,及证明第一次出现sum的下标到此时sum组成的连续子数组包含相同0和1
if (map.containsKey(sum)) {
res = Math.max(res, i - map.get(sum));
} else {
// 仅记录第一次前缀和出现的下标,不更新后续出现位置
map.put(sum, i);
}
}
return res;
}
}
结果如下:
网友评论