算法通关村——滑动窗口高频问题

最长子串专题

无重复字符的最长子串

这道题目对应的就是的滑动窗口，这个就是 滑动窗口 是变化地类型这种算法

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0;
        char[] chars = s.toCharArray();
        int len = s.length();
        int res = 0;
        while (right < len) {
            if (map.containsKey(chars[right])) {
                // 这里为什么是需要取 max ？
                left = Math.max(left, map.get(chars[right]) + 1);
            }
            map.put(chars[right], right);
            res = Math.max(res, right - left + 1);
            right++;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这里为什么需要取 max ？

因为当我们遇到一些特殊情况下，比如 abba 这种情况下，我们会发现如果直接写 left = map.get(chars[right]) + 1 的情况下我们就会发现 以下的情况

会出现错误，所以需要整

至多包含两个不同字符的最长子串

LeetCode159

我们在这里使用 滑动窗口 + K-V 结构实现了算法

我们使用的 Collections.min(map.values()) 就是为了找到对应的 最小的值 然后把 index 最小删除，然后我们就 left = index + 1 ，由于可以找到最小值之后就可以获取到最大的长度的字符串了

Class Solution {
    public int lengthOfLongestSubstringTwoDistinct3(String s) {
        int left = 0, right = 0;
        // 最长的长度
        int maxLen = 2;
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        while (right < s.length()) {
            // 当我们包含不包含两个支付
            if (map.size() < 3) {
                map.put(chars[right], right++);
            }
            // 当我们的 map 到达了 3 的时候我们就需要一些操作
            if (map.size() == 3) {
                // 我们需要把把 map 的最小的值拿到，这个值就是需要删除的值
                int delIndex = Collections.min(map.values());
                map.remove(chars[delIndex]);
                left = delIndex + 1;
            }
            
            maxLen = Math.max(maxLen, right - left);
        }
        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

至多包含 K 个不同字符的最长子串

LeetCode340

题目的完整要求是：给定一个字符串 s，找出 至多 包含 k 个不同字符的最长子串T。示例：

输入: s = "eceba", k = 2
输出: 3
解释: 则 T 为 "ece"，所以长度为 3。
1
2
3

这个就是可以修改上面的代码就可以实现

Class Solution {
    public int lengthOfLongestSubstringTwoDistinct3(String s, int k) {
        int left = 0, right = 0;
        // 最长的长度
        int maxLen = 2;
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        while (right < s.length()) {
            // 当我们包含不包含 k 个支付
            if (map.size() < k + 1) {
                map.put(chars[right], right++);
            }

            if (map.size() == k + 1) {
                // 我们需要把把 map 的最小的值拿到，这个值就是需要删除的值
                int delIndex = Collections.min(map.values());
                map.remove(chars[delIndex]);
                left = delIndex + 1;
            }
            
            maxLen = Math.max(maxLen, right - left);
        }
        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

长度最小的子数组

209. 长度最小的子数组

找出该数组中满足其总和 「大于等于」 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
    输入：target = 7, nums = [2,3,1,2,4,3]
    输出：2
    解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
    输入：target = 4, nums = [1,4,4]
    输出：1
示例 3：
    输入：target = 11, nums = [1,1,1,1,1,1,1,1]
    输出：0
1
2
3
4
5
6
7
8
9
10

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        int left = 0, right = 0;
        // 初始化为一个足够大的数
        int result = Integer.MAX_VALUE; 
        int sum = 0;

        while (right < nums.length) {
            sum += nums[right];
            while (sum >= target) {
                // 当我们的 sum 「大于等于」target 我们就可以把对应的长度记录下来
                result = Math.min(result, right - left + 1);
                // 把最左边的值剔除
                sum -= nums[left];
                // 右指针右移
                left++;
            }
            right++;
        }
        // 当我们 result == Integer.MAX_VALUE 时候，返回的就是 0 
        // 而且这个值非常的大我们不用担心 nums 的所有的值加起来，不可能能达到 Integer.MAX_VALUE 
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}   
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

盛水最多的容器

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

说明：你不能倾斜容器。

垂线容器问题的核心在于，容器的面积受到两个因素的影响：容器的宽度和容器两侧较低的垂线的高度。在每一步中，我们移动指针来改变容器的宽度，并且我们希望移动指针以便获得更高的垂线。

考虑以下情况：

1. 如果我们保持容器的宽度不变，即不移动任何指针，那么容器的面积将取决于两侧较低的垂线的高度，这时可能是最大的高度。

2. 如果我们向内移动指针，减小容器的宽度，那么容器的面积就会减小，因为宽度变小了。
   但如果我们向内移动指针，并且高度也变得更高，那么容器的面积可能会增大。这是因为宽度减小，但高度增大，这种情况下可能会获得更大的面积。

因此，为了找到最大的容器面积，我们在每一步中移动指针的目标是，如果可能的话，找到更高的垂线，即增大高度，并在同时尽量保持宽度足够大。这就是为什么向内移动指针面积可能会增大的原因，因为我们希望在高度增加的情况下，通过减小宽度来找到更大的面积。这正是双指针法的关键之处。

所以我们就是把指针往里面移动，这样就能找到更大地面积，同时我们不选这只使用一个指针地策略，因为那种解法很容易就会出现运行时间过长地问题

class Solution {
    public int maxArea(int[] height) {
        int len = height.length;
        int left = 0, right = len - 1;
        int res = 0;
        
        while (left < right) {
            res = height[left] < height[right] ?
                    Math.max(res, (right - left) * height[left++]) :
                    Math.max(res, (right - left) * height[right--]);
        } 
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

寻找子串异位词（排列）

如果两个字符串仅仅是字母出现的位置不一样，则称两者相互为对方的一个排列，也称为异位词。如果判断两个字符串是否互为排列，是字符串的一个基本算法

字符串的排列

LeetCode567 Medium

给你两个字符串s1和s2 ，写一个函数来判断 s2是否包含 s1的排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的子串 。其中s1和s2都只包含小写字母。

示例：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
1
2
3
4

一般的思路就是通过创建一个和 s1 一样的的窗口遍历，但是这样有一个问题就是效率不是很高，我们可以使用一个数组

我们可以创建一个大小为26的数组，每个位置就存储从a到z的个数，为了方便操作，索引我们使用

index = s1.charAt(i) - ‘a’

来表示，这是处理字符串的常用技巧。一定要记住

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int sLen1 = s1.length(), sLen2 = s2.length();
        if (sLen1 > sLen2) {
            return false;
        }
        int[] charArray1 = new int[26];
        int[] charArray2 = new int[26];
        //先读最前面的一段来判断。
        for (int i = 0; i < sLen1; ++i) {
            charArray1[s1.charAt(i) - 'a']++;
            charArray2[s2.charAt(i) - 'a']++;
        }

        if (Arrays.equals(charArray1, charArray2)) {
            return true;
        }
        for (int right = sLen1; right < sLen2; ++right) {
            charArray2[s2.charAt(right) - 'a']++;
            int left = right - sLen1;
            charArray2[s2.charAt(left) - 'a']--;
            if (Arrays.equals(charArray1, charArray2)) {
                return true;
            }
        }
        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

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

题目： LeetCode438

这个的思路和上面的思路一致

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<>();
        }
        List<Integer> ans = new ArrayList<>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        //先分别初始化两个数组
        for (int i = 0; i < pLen; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int left = 0; left < sLen - pLen; left++) {
            sCount[s.charAt(left) - 'a']--;
            int right = left + pLen;
            sCount[s.charAt(right) - 'a']++;

            if (Arrays.equals(sCount, pCount)) {
                //上面left多减了一次，所以
                ans.add(left + 1);
            }
        }
        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
30
31

这里的问题主要是为什么需要 ans.add(left + 1) 这里的 left 为什么需要加 1 ？

当我们进行把对应的「窗口」向右移动的时候，我们需要先把最左边的剔除出去。比如 “eabc” 和 “abc” 我们的 left 指针应该就在索引为 0 的位置，我们需要添加到对应的列表之中，我们就需要放入索引为 1 的位置，所以需要 left + 1