【每日练习系列】—— 滑动窗口与数学模拟

3. 无重复字符最长子串

利用 HashMap 来存储字符串中的元素与出现的位置，每遍历一个元素，就将其添加到哈希表中，Key 为字符 —— Value 为元素当前的位置。

利用滑动的窗口来记录不重复子串的长度，left 定义为左边界。
当哈希表中存在了当前的字符，那么就更新左边界的位置，此时分为两种情况：

left = Math.max(left, map.get(ch) + 1);
1

（1）找到上次出现该字符的位置，将左边界移动到该位置的右边
（2）可能移动后的位置在当前左边界的左边，如果这样就不更新左边界

记录最大无重复子串的长度maxLen = Math.max(maxLen, i - left + 1);

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //字符串长度为零
        if(s.length() == 0){
            return 0;
        }
        //设置哈希表，记录元素与对应的位置
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        //设置滑动窗口左边界
        int left = 0;
        //记录最大长度
        int maxLen = 0;
        //遍历字符串
        for(int i = 0; i < s.length(); i++){
            //获取当前字符
            char ch = s.charAt(i);
            //判断是否存在于map中
            if(map.containsKey(ch)){
                //更新左边界，第一次出现ch的位置+1，如果更新后的边界小于现在的左边界则不更新
                left = Math.max(left, map.get(ch) + 1);
            }
            //将当前字符添加到map中[已经存在了就更新索引位置]
            map.put(ch, i);
            //更新最大长度
            maxLen = Math.max(maxLen, i - left + 1);
        }
        //返回结果
        return maxLen;
    }
}
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

567. 字符串的排列

• 滑动窗口的大小就是 s1 的大小
• 遍历字符串，在 s2 中截取和窗口长度相同大小的子串
• 调用方法通过两个字符串的组成是否相同来比较。【固定窗口大小】

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        //滑动窗口的大小
        int left = 0;
        int right = s1.length();
        //保存结果
        boolean res = false;
        //遍历字符串s2
        while(right <= s2.length()){
            //判断当前窗口是否符合条件
            res = isSame(s1, s2.substring(left, right));
            if(res){
                break;
            }
            left++;
            right++;
        }
        return res;

    }
    //判断两个字符串的组成是否相同
    public boolean isSame(String s1, String s2){
        //记录每个字母出现的次数
        int [] num = new int[26];
        //遍历s2串
        for(int i = 0; i < s2.length(); i++){
            char c = s2.charAt(i);
            num[c - 'a']++;
        }
        //遍历s1串
        for(int j = 0; j < s1.length(); j++){
            char ch = s1.charAt(j);
            if(--num[ch - 'a'] < 0){
                return false;
            }
        }
        return true;
    }
}
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

828. 统计子串中的唯一字符

    public int uniqueLetterString(String s) {
        //存储last字符前一个字符所在位置
        int[] lastIndexMap = new int[26];
        //存储cur字符当前所处位置
        int[] curIndexMap = new int[26];
        Arrays.fill(lastIndexMap, -1);
        Arrays.fill(curIndexMap, -1);
        char[] chars = s.toCharArray();
        int ans = 0;
        for (int i = 0; i < chars.length; i++) {
            //next字符
            int index = chars[i] - 'A';
            //cur字符的索引不是-1，计算cur字符的贡献值
            if (curIndexMap[index] > -1) {
                ans += (i - curIndexMap[index]) * (curIndexMap[index] - lastIndexMap[index]);
            }
            //滚动存放cur和last
            lastIndexMap[index] = curIndexMap[index];
            curIndexMap[index] = i;
        }
        //计算最后next字符的贡献值，最后一个位置就是s.length()
        for (int i = 0; i < 26; i++) {
            if (curIndexMap[i] > -1) {
                ans += (curIndexMap[i] - lastIndexMap[i]) * (s.length() - curIndexMap[i]);
            }
        }
        return ans;
    }

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