stellogic的个人空间
滑动窗口
stellogic Two
  2025-09-20 11:46:19   2025-09-20 11:46:19    

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

思考：遍历每个字符，以它作为起点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int maxLen = 0;
        for (int i = 0; i < chars.length; i++) {
            Set<Character> selected = new HashSet<>();
            int maxLenThisLoop = 0;
            int j = i;
            while (j < chars.length && !selected.contains(chars[j])){
                selected.add(chars[j]);
                maxLenThisLoop++;
                j++;
            }
            maxLen = Math.max(maxLen,maxLenThisLoop);
        }
        return maxLen;

    }
}

这个解法时间复杂度是O(n^2)
但是存在很多重复计算
比如abcdeafg，先计算了abcde，之后从b开始作为起点再次计算，但实际上我们已经知道bcde是不重复的，不必再次验证。

更好的方法是滑动窗口。

滑动窗口的核心思想是维护一个“窗口”，这个窗口内的元素始终是无重复的。我们通过移动窗口的右边界来扩大窗口，当遇到重复字符时，再移动左边界来缩小窗口，直到窗口内没有重复字符为止。在这个过程中，我们不断记录并更新窗口的最大长度。

  1. 用set来记录窗口
  2. 使用两个指针，left和right，使用maxLength记录最大长度
  3. 每次把right指针指向的元素处理，有重复就left指针右移动，直到没重复，没重复就把maxLength更新
  4. 重复3直到right指向最右端元素
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
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> characterSet = new HashSet<>();
        int left  = 0;
        int right = 0;
        int maxLength = 0;
        char[] chars = s.toCharArray();
        while (left <= right && right < chars.length)
        {
            if (!characterSet.contains(chars[right]))
            {
                characterSet.add(chars[right]);
                maxLength = Math.max(maxLength,right - left + 1);
                right++;
            }else {
                characterSet.remove(chars[left]);
                left++;
            }
        }
        return maxLength;
    }
}

时间复杂度O(n)
空间复杂度O(k),k是不同字符的个数

438. 找到字符串中所有字母异位词

给定两个字符串 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” 的异位词。

提示:

1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

考虑滑动窗口，依次遍历，每个状态判断是否是字母异位词

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
import java.util.*;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int left = 0;
        int right = left +p.length() - 1;
        char[] sCharArray = s.toCharArray();
        char[] p_sortedArray = p.toCharArray();
        Arrays.sort(p_sortedArray);
        String p_sortedString = new String(p_sortedArray);
        while (left <= right && right < sCharArray.length) {
            char[] subChars_sortedArray =  s.substring(left,right + 1).toCharArray();
            Arrays.sort(subChars_sortedArray);
            String subChars_sortedString = new String(subChars_sortedArray);
            if (subChars_sortedString.equals(p_sortedString))
            {
                result.add(left);
            }
            left++;
            right++;
        }
        return result;
    }
}

注意：

  1. Arrays.sort的返回值是void。排序的正确做法是先创建一个数组，然后调用Arrays.sort(chars)
  2. 对对象调用toString()得到的是一个哈希码，这个哈希码是类似于把对象地址利用哈希算法转换成的一个键（一个字符串）。因此对chat[]调用toString()得到的不是字符串本身，而是一个哈希码。
  3. 获取子字符串使用subString方法，包含begin不含end
  4. Arrays.equals() 和 String.equals() 的时间复杂度都是 O(k)，其中 k 是两个被比较对象的长度。
  5. 时间复杂度O(n*mlogm),n是s的长度，m是p的长度

优化：
更好的方法是计数法

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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int[] pCount = new int[26];
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }
        int left = 0;
        int right = left + p.length() - 1;
        while (left <= right && right < s.length()) {
            char[] sSubStringArray = s.substring(left, right + 1).toCharArray();
            int[] sCount = new int[26];
            for (char c : sSubStringArray) {
                sCount[c - 'a']++;
            }
            if (Arrays.equals(pCount,sCount)){
                result.add(left);
            }
            
            left++;
            right++;
        }
        return result;
    }
}
  1. 注意：sCount必须在循环内创建，确保每次都是新的
  2. 时间复杂度O(n*m),n是s的长度，m是p的长度。

可以继续优化。不必每次都创建sCount数组，因为每次窗口滑动后，只有一个字符进来，一个字符出去，只需要修改这两个字符的计数即可

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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length())
        {
            return new ArrayList<Integer>(0);
        }
        List<Integer> result = new ArrayList<>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }
        int left = 0;
        int right = left + p.length() - 1;
        char[] sCharArray = s.toCharArray();
        for (int i = left; i <= right; i++) {
            sCount[sCharArray[i] - 'a']++;
        }
        while (left <= right && right < s.length()) {
            if (Arrays.equals(sCount,pCount)){
                result.add(left);
            }
            left++;
            right++;
            if (right < s.length()) {
                sCount[sCharArray[left - 1] - 'a']--;
                sCount[sCharArray[right] - 'a']++;
            }
        }
        return result;
    }
}

时间复杂度O(n)
空间复杂度O(1)，因为计数数组的大小是固定的26

还可以继续优化，避免每次循环调用Arrays.equals()，因为这个方法的时间复杂度是O(26)，虽然是常数，但仍然可以优化掉。

不再使用sCount和pScount，使用一个count数组，count[i]表示字符’i’在当前窗口中出现的次数与在p中出现的次数之差。再引入一个differ，differ表示count数组中非零元素的个数。(也就是当前窗口与p在字符组成上有差异的字符种类数)

可以认为p中的字符出现一次就让count对应的位置减一，s中字符出现一次就让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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length()) {
            return new ArrayList<>(0);
        }
        List<Integer> result = new ArrayList<>();
        int[] count = new int[26];
        int differ = 0;
        for (int i = 0; i < p.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[p.charAt(i) - 'a']--;
        }
        for (int i : count) {
            if (i != 0)
            {
                differ++;
            }
        }
        int left = 0;
        int right = left + p.length() - 1;
        
        while (right < s.length()) {
            if (differ == 0) {
                result.add(left);
            }
            left++;
            right++;
            if (right < s.length())
            {
                char charOut = s.charAt(left-1);
                char charIn = s.charAt(right);
                if (charIn == charOut){
                    continue;
                }else {
                    //先处理charout
                    if (count[charOut - 'a'] == 0){
                        differ++;
                    }else if (count[charOut - 'a'] == 1){
                        differ--;
                    }
                    //处理charIn
                    if (count[charIn - 'a'] == 0){
                        differ++;
                        
                    } else if (count[charIn - 'a'] == -1) {
                        differ--;
                        
                    }
                    count[charOut - 'a']--;
                    count[charIn - 'a']++;
                }
            }
        }
        return result;
    }
}

时间复杂度还是O(n),但是避免了每次调用Arrays.equals()，因此效率更高
空间复杂度O(1)

滑动窗口
2025/09/20/滑动窗口/
作者
stellogic
发布于
2025-09-20 11:46
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 1. 无重复字符的最长子串
  2. 2. 438. 找到字符串中所有字母异位词
  1. 1. 无重复字符的最长子串
  2. 2. 438. 找到字符串中所有字母异位词