hot100之子串
和为K的子数组(560)先看代码
class Solution {
public int subarraySum(int[] nums, int k) {
int res = 0;
int preSum = 0;
Map<Integer, Integer> cnt = new HashMap<>(nums.length);
for (int num : nums){
cnt.merge(preSum, 1, Integer::sum);
preSum += num;
res += cnt.getOrDefault(**preSum - k**, 0);
}
return res;
}
}
[*]分析
cnt用来记录相同前缀和的前缀数量
一次循环一边更新相同前缀和的前缀数量, 一边将吻合的数据放入res
preSum - k 是前缀和的关键
[*]感悟
只有”单调”的数据集才适合用滑动窗口, 非”单调”的前缀和才好做 , 否则每次移动窗口都带来混乱
“单调”指的是 任意 num>0且单调递增 OR 任意 num < 0 且单调递减
不符合单调
符合单调
滑动窗口最大值(560)
先看代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int;
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0; i < n; i++){
while (!queue.isEmpty() && nums <= nums){
queue.removeLast();
}
queue.addLast(i);
if (i-k >= queue.getFirst()){
queue.removeFirst();
}
if(i-k+1 >= 0) res = nums;
}
return res;
}
}
[*]分析
通过维护单调递减队列queue
队列中存储数据下标
[*]感悟
很多题目都是通过存储下标 因为一个下标含有两个有效数据 → </strong>
最小覆盖字串(076)
先看代码
class Solution {
public String minWindow(String s, String t) {
int needCnt = 0;
int[] need = new int;
for (char c : t.toCharArray()){
if (need == 0){
needCnt++;
}need++;
}
int n = s.length();
int resLef = -1;
int resRig = n;
int lef = 0;
for (int rig = 0; rig < n; rig++){
char cR = s.charAt(rig);
need--;
if (need == 0){
needCnt--;
}
while (needCnt == 0){
if(resRig-resLef > rig-lef){
resLef = lef;
resRig = rig;
}
char cL = s.charAt(lef);
if (need == 0) needCnt++;
need++;
lef++;
}
}
return resLef < 0 ? "" : s.substring(resLef, resRig+1);
}
}
[*]分析
通过滑动窗口遍历
通过数组need存储需要各种类字符数量, needCnt 存储需要的字符种类
[*]感悟
施工中…
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]