滑动窗口

滑动窗口

Jason Lv3

643. 子数组最大平均数 I

以下会超时 因为每个子数组都要计算一次平均数,复杂度为O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public double findMaxAverage(int[] nums, int k) {
if(nums.length==1) return (double)nums[0];
double maxm = 0;
int fast = k-1;
int slow = 0;
while(fast<nums.length){
double temp = 0;
for(int i=0;i<k;i++){
temp+= nums[slow+i];
}
temp = temp/k;
if(temp>maxm) maxm = temp;
fast++;
slow++;
}
return maxm;
}
}

以下为官方答案 两头更新 中间的保留

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
for(int i=0;i<k;i++){
sum+=nums[i];
}
int maxm = sum;
for(int j=k;j<nums.length;j++){
sum = sum - nums[j-k] + nums[j];
if(sum>maxm) maxm = sum;
}
return 1.0*maxm/k;
}
}

1004. 最大连续1的个数 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int longestOnes(int[] nums, int k) {
int right = 0;
int res=0;
int left = 0;
int count = 0;
while(right<nums.length){
if(nums[right]==0) count++;
while(count>k){
if(nums[left]==0) count--;
left++;
}
res = Math.max(res,right-left+1);
right++;
}
return res;
}
}

1493. 删掉一个元素以后全为 1 的最长子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int longestSubarray(int[] nums) {
int right = 0,left = 0;
int res = 0;
int c=0;
while(right<nums.length){
if(nums[right]==0) c++;
while(c>1){
if(nums[left]==0) c--;
left++;
}

res =Math.max(res,right-left);
right++;
}
return res;
}
}

滑动窗口模版

右指针主动走 左指针通过判断条件被动走

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findSubArray(nums):
N = len(nums) # 数组/字符串长度
left, right = 0, 0 # 双指针,表示当前遍历的区间[left, right],闭区间
sums = 0 # 用于统计 子数组/子区间 是否有效,根据题目可能会改成求和/计数
res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
while 区间[left, right]不符合题意: # 此时需要一直移动左指针,直至找到一个符合题意的区间
sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
left += 1 # 真正的移动左指针,注意不能跟上面一行代码写反
# 到 while 结束时,我们找到了一个符合题意要求的 子数组/子串
res = max(res, right - left + 1) # 需要更新结果
right += 1 # 移动右指针,去探索新的区间
return res

3. 滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap<Character,Integer>();
int maxm = 0;
int left=0;
for(int i=0;i<s.length();i++){
if(map.containsKey(s.charAt(i))){
left = Math.max(left,map.get(s.charAt(i))); //max保证left不能往回跳
}
map.put(s.charAt(i),i);
maxm = Math.max(maxm,i-left+1);
}
return maxm;
}
}

438. 比特位计数

很棒!自己调试ac的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public List<Integer> findAnagrams(String s, String p) {
char charp[] = p.toCharArray();
Arrays.sort(charp);
List<Integer> list = new ArrayList<Integer>();
String p1 = new String(charp);
int left=0;
int right=p.length()-1;
while(right<s.length()){
String temp = s.substring(left,right+1);
char charpp[] = temp.toCharArray();
Arrays.sort(charpp);
String p2 = new String(charpp);
if(p1.equals(p2)){
list.add(left);
}
left++;
right++;
}
return list;
}
}
  • Title: 滑动窗口
  • Author: Jason
  • Created at : 2023-09-13 16:12:34
  • Updated at : 2023-09-18 21:05:35
  • Link: https://xxxijason1201.github.io/2023/09/13/LeetCode/滑动串口/
  • License: This work is licensed under CC BY-NC-SA 4.0.
 Comments