算法模板之滑动窗口系列

Algorithm , 评论

最小覆盖子串

难度:困难

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

滑动窗⼝算法的思路是这样：
1、 我们在字符串 S 中使⽤双指针中的左右指针技巧， 初始化 left = right =0， 把索引闭区间 [left, right] 称为⼀个「窗⼝」 。
2、 我们先不断地增加 right 指针扩⼤窗⼝ [left, right]， 直到窗⼝中的字符串符合要求（包含了 T 中的所有字符） 。
3、 此时， 我们停⽌增加 right， 转⽽不断增加 left 指针缩⼩窗⼝ [left,right]， 直到窗⼝中的字符串不再符合要求（不包含 T 中的所有字符了） 。同时， 每次增加 left， 我们都要更新⼀轮结果。
4、 重复第 2 和第 3 步， 直到 right 到达字符串 S 的尽头。

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
public String minWindow(String s, String t) {
        Map<Character, Integer> needs = new HashMap<>(), window = new HashMap<>();
        for(int i = 0; i < t.length(); i++){
            needs.put(t.charAt(i), needs.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0, right = 0;
        int start = 0; // 最小覆盖子串的起始下标
        int len = Integer.MAX_VALUE; // 最小覆盖子串的长度

        int valid = 0; // 统计有多少字符满足了覆盖的要求
        while(right < s.length()){
            // 当前要加入窗口的字符
            char c = s.charAt(right);
            right++; //  右指针++
            if(needs.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 看看字符数量是否达到要求
                if(window.get(c).equals(needs.get(c)))   valid++;  // 千万注意别用 ==  判断...
            }
            // 看看是否满足要求
            while(valid == needs.size()){
                // 在这里更新最小覆盖子串
                if(right - left < len){
                    start = left;
                    len = right - left;
                }
                char lc = s.charAt(left);
                left++; //  左指针++
                if(needs.containsKey(lc)){
                    // 看看字符数量是否达到要求
                    if(window.get(lc).equals(needs.get(lc)))   valid--;   
                    window.put(lc, window.getOrDefault(lc, 0) - 1);
                }
            }

        }

        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start+len);
//        s.substring()

    }

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

leetcode438, 难度: 中等

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

  • 字母异位词指字母相同，但排列不同的字符串。
  • 不考虑答案输出的顺序。

示例 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
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 t) {
        Map<Character, Integer> needs = new HashMap<>(), window = new HashMap<>();
        for(int i = 0; i < t.length(); i++){
            needs.put(t.charAt(i), needs.getOrDefault(t.charAt(i), 0) + 1);
        }
        int left = 0, right = 0;
        List<Integer> res = new ArrayList<>();
   
        int valid = 0; // 统计有多少字符满足了覆盖的要求
        while(right < s.length()){
            // 当前要加入窗口的字符
            char c = s.charAt(right);
            right++; //  右指针++
            if(needs.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);
                // 看看字符数量是否达到要求
                if(window.get(c).equals(needs.get(c)))   valid++;
            }
            // 看看是否满足要求
            while(right - left  >= t.length()){
                if(valid == needs.size()){
                    res.add(left);
                    
                }
                char lc = s.charAt(left);
                left++; //  左指针++
                if(needs.containsKey(lc)){
                    // 看看字符数量是否达到要求
                    if(window.get(lc).equals(needs.get(lc)))   valid--;
                    window.put(lc, window.getOrDefault(lc, 0) - 1);
                }
            }

        }
        return res;

    }
}

无重复字符的最长子串

难度中等,leetcode3

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

方法一

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lengthOfLongestSubstring(String s) {
       Map<Character, Integer> window = new HashMap<>();

       int left = 0, right = 0;
       int res = Integer.MIN_VALUE;
       while( right < s.length()){
           char c = s.charAt(right);
           right++;
           window.put(c, window.getOrDefault(c, 0) + 1);
           while( window.get(c).compareTo(1) >  0){
               // 有重复 需要缩小窗口
               char l = s.charAt(left);
               window.put(l, window.get(l) - 1);
               left++;
           }
           res = Math.max(res, right - left);
       }
       return res == Integer.MIN_VALUE ? 0 : res;
   }

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] charIndex = new int[256];
        int res = 0;
        int len = s.length();
        for(int left = 0, right = 0; right < len; right++){
            char c = s.charAt(right);
            
            left = Math.max(left, charIndex[c]);
            res = Math.max(res, right - left + 1);

            charIndex[c] =  right+1;

        }
        return res;
    }
       
}

剑指 Offer 57 - II. 和为s的连续正数序列

难度：简单

输入一个正整数 target ，输出所有和为 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

public int[][] findContinuousSequence(int target) {
    List<int[]> res = new ArrayList<>();
    int len  = (int)Math.ceil(target/2.0);
    for(int i = 1; i <= len;i++){
        List<Integer> ans = new ArrayList<>();
        int sum = 0;
        boolean flag = false;
        for(int j  = i; j <= len; j++){
            sum+= j;
            ans.add(j);
            if(sum == target){
                flag = true;
                break;
            }
        }
        if(flag){
            int[] a = ans.stream().mapToInt(Integer::valueOf).toArray();
            res.add(a);
        }
    }

   return res.toArray(new int[res.size()][]);
}

法二

滑动窗口

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

// 滑动窗口
 public int[][] findContinuousSequence(int target) {
    List<int[]> res = new ArrayList<>();
    
    int l = 1;
    int r  = 1;
    int sum = 0;
    while(r  <=  target/2+1){
        // 求和
        int[] a = new int[r-l+1];
        for(int i = l ; i <= r; i++){
            sum+=i;
        }
        if(sum > target){
            l++;
        }else if(sum < target){
            r++;
        }else{
            int k = 0;
             for(int i = l ; i <= r; i++){
                a[k++] = i;
            }
            res.add(a);
            l++;
        }
        sum = 0;
    }

   return res.toArray(new int[res.size()][]);
}


朱宏梁Research & Develop

后端开发工程师