滑动窗口
# 3. 无重复字符的最长子串 (opens new window)
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] window = new int[256];
int l=0,r=0;
int ans = 0;
while(r<s.length()){
char c1 = s.charAt(r++);
window[c1]++;
while(window[c1]>1){
char c2 = s.charAt(l++);
window[c2]--;
}
ans = Math.max(ans,r-l);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 209. 长度最小的子数组 (opens new window)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int sum=0,l=0;
int ans = Integer.MAX_VALUE;
for(int r=0;r<n;r++){
sum += nums[r];
while(sum>=target){
ans = Math.min(ans,r-l+1);
sum -= nums[l++];
}
}
return ans == Integer.MAX_VALUE?0:ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 713. 乘积小于 K 的子数组 (opens new window)
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if(k<=1) return 0;//k为0，左指针越界
int n = nums.length;
int ans=0,mul=1,l=0;
for(int r=0;r<n;r++){
mul *= nums[r];
while(mul>=k){
mul /= nums[l++];
}
ans += r-l+1;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 424. 替换后的最长重复字符 (opens new window)
class Solution {
public int characterReplacement(String s, int k) {
int n = s.length();
int l=0,r=0,ans=0;
int max=0;
int[] cnt = new int[26];
while(r<n){
int i=s.charAt(r)-'A';
cnt[i]++;
max = Math.max(max,cnt[i]);
while(r-l+1 > max+k){
cnt[s.charAt(l)-'A']--;
l++;
}
ans = Math.max(ans,r-l+1);
r++;
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 76. 最小覆盖子串 (opens new window)
class Solution {
public String minWindow(String s, String t) {
Map<Character,Integer> need = new HashMap<>();
Map<Character,Integer> window = new HashMap<>();
for(int i=0;i<t.length();i++){
char c = t.charAt(i);
need.put(c,need.getOrDefault(c,0)+1);
}
int l=0,r=0;
int len = Integer.MAX_VALUE;
int cnt=0;// 记录字母种类
int resIndex=0;
while(r<s.length()){
char c1 = s.charAt(r++);
if(need.containsKey(c1)){
window.put(c1,window.getOrDefault(c1,0)+1);
if(window.get(c1).equals(need.get(c1))){
cnt++;
}
}
// 达到缩小窗口条件
while(cnt == need.size()){
if(r-l<len){
resIndex = l;
len = r-l;
}
char c2 = s.charAt(l++);
if(need.containsKey(c2)){
if(window.get(c2).equals(need.get(c2))){
cnt--;
}
window.put(c2,window.get(c2)-1);
}
}
}
return len == Integer.MAX_VALUE?"":s.substring(resIndex,resIndex+len);
}
}
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
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
# 438. 找到字符串中所有字母异位词 (opens new window)
class Solution {
public List<Integer> findAnagrams(String s, String p) {
Map<Character,Integer> window = new HashMap<>();
Map<Character,Integer> need = new HashMap<>();
for(int i=0;i<p.length();i++){
char c = p.charAt(i);
need.put(c,need.getOrDefault(c,0)+1);
}
int l=0,r=0;
int cnt=0;
List<Integer> res = new ArrayList<>();
while(r<s.length()){
char c1 = s.charAt(r++);
if(need.containsKey(c1)){
window.put(c1,window.getOrDefault(c1,0)+1);
if(window.get(c1).equals(need.get(c1))){
cnt++;
}
}
while(r-l==p.length()){
if(cnt == need.size()){
res.add(l);
}
char c2 = s.charAt(l++);
if(need.containsKey(c2)){
if(window.get(c2).equals(need.get(c2))){
cnt--;
}
window.put(c2,window.get(c2)-1);
}
}
}
return res;
}
}
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
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
# 567. 字符串的排列 (opens new window)
class Solution {
public boolean checkInclusion(String s1, String s2) {
Map<Character,Integer> window = new HashMap<>();
Map<Character,Integer> need = new HashMap<>();
for(int i=0;i<s1.length();i++){
char c1 = s1.charAt(i);
need.put(c1,need.getOrDefault(c1,0)+1);
}
int l=0,r=0;
int cnt=0;
while(r<s2.length()){
char c1 = s2.charAt(r++);
if(need.containsKey(c1)){
window.put(c1,window.getOrDefault(c1,0)+1);
if(window.get(c1).equals(need.get(c1))){
cnt++;
}
}
while(r-l==s1.length()){
if(cnt==need.size()){
return true;
}
char c2 = s2.charAt(l++);
if(need.containsKey(c2)){
if(window.get(c2).equals(need.get(c2))){
cnt--;
}
window.put(c2,window.get(c2)-1);
}
}
}
return false;
}
}
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
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