注： 仅记录模板题，滑动窗口非这些题目的最佳解(不如说大部分都可以优化。。)
滑动窗口模板
步骤：
- 根据题意维护变量
- 和 Sum
- 最大长度 max_len，最小长度 min_len
- 注意： 有的时候要设
Integer.MAX_VALUE/Integer.MIN_VALUE
- 不重复 hashmap = {}
- 等
- 窗口的开始位置start和结束位置end
- 根据条件写判断语句，维护step1中的变量
- 根据题目要求，从中选择一种方法套用
- 选择一：窗口长度固定
if 窗口长度达到限定的长度：
1.更新step1中的相关变量
2.窗口左边位置start向前移动 1，保证end向右移动时窗口长度保持不变
- 选择二：窗口长度不固定
while 窗口条件不符合：
1.更新step1中的相关变量
2.不断移动start，直到窗口条件符合
- 返回答案
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数
示例如下:
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
**解题思路：**通过滑动窗口算法找到长度为k的连续子数组的最大和，再除以k，得到结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
double avg = Integer.MIN_VALUE;
int start = 0;
for (int end = 0; end < nums.length; end++) {
sum += nums[end];
if (end - start + 1 == k) {
avg = Math.max(1.0 *sum/k, avg);
}
if (end - start + 1>=k) {
sum -= nums[start];
start += 1;
}
}
return avg;
}
}
|
注意浮点数精度，要用double
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度 。
示例如下:
输入：s = “abcabcbb”
输出：3
解释：因为无重复字符的最长子串是 “abc”，所以其长度为 3。
**解题思路：**题目中提到不重复字符串，所以引入哈希表存储，key存储元素，value存储出现的次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLen = 0;
Map<Character,Integer> myMap = new HashMap<>();
int start = 0;
char[] st = s.toCharArray();
for (int end = 0; end < s.length(); end++) {
int k = myMap.getOrDefault(st[end], 0) + 1;
myMap.put(st[end],k);
if (myMap.size()==end-start+1) {
maxLen = Math.max(end-start+1, maxLen);
}
while (myMap.size()<end-start+1) {
int val = myMap.get(st[start]);
val--;
if (val==0) {
myMap.remove(st[start]);
}else{
myMap.put(st[start], val);
}
start++;
}
}
return maxLen;
}
}
|
给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 **连续子数组 [numsl, numsl+1, …, numsr-1, numsr] **，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例如下:
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
**解题思路：**通过滑动窗口算法找到连续子数组的和 >=target的最小长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int minSubArrayLen(int target, int[] nums) {
int minLen = Integer.MAX_VALUE;
int sum = 0;
int start = 0;
for (int end = 0; end < nums.length; end++) {
sum += nums[end];
if (sum>=target) {
minLen = Math.min(minLen, end - start + 1);
}
while (sum>=target) {
minLen = Math.min(minLen, end - start + 1);
sum -= nums[start];
start ++;
}
}
return minLen==Integer.MAX_VALUE?0:minLen;
}
}
|
给你一个正整数数组 nums ，请你从中删除一个含有若干不同元素的子数组。删除子数组的得分就是子数组各元素之和 。
返回 只删除一个子数组可获得的最大得分。
如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],…,a[r] ，那么它就是 a 的一个子数组。
示例如下:
输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]
输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]
**解题思路：**只需求不重复的连续子数组的最大和即可，类似Lc3,只是多维护了个Sum和变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public int maximumUniqueSubarray(int[] nums) {
// step1
int max = 0;
int sum = 0;
Map<Integer, Integer> myMap = new HashMap<>();
// step2
int start = 0;
for (int end = 0; end < nums.length; end++) {
int val1 = myMap.getOrDefault(nums[end], 0) + 1;
myMap.put(nums[end], val1);
sum += nums[end];
// step3
if (end - start + 1 == myMap.size() ) {
max = Math.max(max, sum);
}
while (end - start + 1 > myMap.size()) { // 说明包含重复项
int val2 = myMap.get(nums[start]);
val2--;
if (val2 == 0) {
myMap.remove(nums[start]);
}else{
myMap.put(nums[start], val2);
}
sum -= nums[start];
start++;
}
}
return max;
}
}
|
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例1:
输入：s = “cbaebabacd”, p = “abc”
输出：[0,6]
解释：起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例2:
输入：s = “abab”, p = “ab”
输出：[0,1,2]
解释：起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
**解题思路：**滑动窗口满足窗口的所有元素及个数都和目标串一致，滑动窗口的start值即为答案
示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
char[] st = s.toCharArray();
Map<Character, Integer> sMap = new HashMap<>();
Map<Character, Integer> pMap = new HashMap<>();
for (char c : p.toCharArray()) {
int value = pMap.getOrDefault(c, 0) + 1;
pMap.put(c, value);
}
int i = 0;
for (int j = 0; j < st.length; j++) {
int value = sMap.getOrDefault(st[j], 0) + 1;
sMap.put(st[j], value);
if (j - i + 1 < p.length()) {
continue;
}
if (sMap.equals(pMap)) {
res.add(i);
}
int tmp = sMap.get(st[i]);
tmp--;
if (tmp == 0) {
sMap.remove(st[i]);
} else {
sMap.put(st[i], tmp);
}
i++;
}
return res;
}
}
|
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的 子串 。
示例1:
输入：s1 = “ab” s2 = “eidbaooo”
输出：true
解释：s2 包含 s1 的排列之一 (“ba”)
示例2:
输入：s1= “ab” s2 = “eidboaoo”
输出：false
**解题思路：**类似Lc438
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s2.length()<s1.length()) {
return false;
}
Map<Character, Integer> m1 = new HashMap<>();
Map<Character, Integer> m2 = new HashMap<>();
int i = 0;
int len = s1.length();
for (int j = 0; j < len; j++) {
int v = m1.getOrDefault(s1.charAt(j), 0) + 1;
m1.put(s1.charAt(j), v);
int v2 = m2.getOrDefault(s2.charAt(j), 0) + 1;
m2.put(s2.charAt(j), v2);
}
if (m1.equals(m2)) {
return true;
}
for (int j = s1.length(); j < s2.length(); j++) {
int valj = m2.getOrDefault(s2.charAt(j), 0) + 1;
m2.put(s2.charAt(j), valj);
int vali = m2.get(s2.charAt(i));
vali--;
if (vali==0) {
m2.remove(s2.charAt(i));
} else {
m2.put(s2.charAt(i), vali);
}
i++;
if (m1.equals(m2)) {
return true;
}
}
return false;
}
}
|
