力扣热题100——一刷day03

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

一、力扣3. 无重复字符的最长子串

使用滑动窗口寻找最长子串，窗口的含义是无重复字符的最长子串这个含义要一直维护，窗口中的元素使用map记录，右指针元素查询map，非重复元素直接加入map，并且右指针右移，count++，若右指针元素在map中出现，则使用res记录当前窗口无重复字符子串的长度，并且在map中找到重复元素的下标，更新map,更新左指针，更新counnt，同时右指针移动一位。重复如上流程直到右指针走到末尾，结果取res和count最大值

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0 || s.length() == 1){
            return s.length();
        }
        Map<Character,Integer> map = new HashMap<>();
        map.put(s.charAt(0),0);
        int count = 1;
        int res = 1;
        for(int i = 0, j = 1; j < s.length();){
            if(map.containsKey(s.charAt(j))){
                res = Math.max(res,count);
                int k = i;
                i = map.get(s.charAt(j)) + 1;
                while(k < i){
                    map.remove(s.charAt(k));k ++;
                }
                map.put(s.charAt(j),j);
                j ++;
                count = j -i;
            }else{
                map.put(s.charAt(j),j);
                j ++;
                count ++;
            }
        }
        return Math.max(res,count);
    }
}
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

二、力扣438. 找到字符串中所有字母异位词

寻找字母异位词最重要的关键是构造key使用哈希表匹配，降低时间复杂度

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        Set<String> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        if(s.length() < p.length()){
            return list;
        }
        int[] arr = new int[26];
        int[] arr1 = new int[26];
        for(int i = 0; i < p.length(); i ++){
            arr[p.charAt(i) - 'a'] ++;
            arr1[s.charAt(i) - 'a'] ++;
        }
        StringBuilder sb = new StringBuilder();
        StringBuilder sb1 = new StringBuilder();
        for(int i = 0; i < 26; i ++){
            if(arr[i] != 0){
                sb.append('a' + i);
                sb.append(arr[i]);
            }
            if(arr1[i] != 0){
                sb1.append('a' + i);
                sb1.append(arr1[i]);
            }
        }
        set.add(sb.toString());
        for(int i = 0, j = p.length(); j < s.length();){
            if(set.contains(sb1.toString())){
                list.add(i);
            }
            arr1[s.charAt(i)-'a'] --; i ++;
            arr1[s.charAt(j)-'a'] ++; j ++;
            sb1.setLength(0);
            for(int k = 0; k < 26; k ++){
                if(arr1[k] != 0){
                    sb1.append('a' + k);
                    sb1.append(arr1[k]);
                }
            }
        }
        if(set.contains(sb1.toString())){
            list.add(s.length()-p.length());
        }
        return list;
    }
}
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
41
42
43
44
45
46

三、滑动窗口模板

import java.util.HashMap;
import java.util.Map;

public class SlidingWindow {
    void slidingWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;
        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            // ...

            /*** debug 输出的位置 ***/
            System.out.println("window: [" + left + ", " + right + ")");
            /********************/

            // 判断左侧窗口是否要收缩
            while (window needs shrink) {
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                // ...
            }
        }
    }
}

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