滑动窗口

• 使用滑动窗口技巧时，考虑清楚三个问题：
  • 窗口内元素是什么？
  • 如何移动窗口的起始位置？
  • 如何移动窗口的终止位置？

剑指 Offer II 016. 不含重复字符的最长子字符串

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

示例 1:

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

示例 2:

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

示例 3:

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。   请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = "" 输出: 0

//窗口内的元素是String s 的子字符串
//起始位置L为该子字符串的最左侧字符的下标
//终止位置R为该子字符串的最右侧字符的下标
//当该子字符串因为纳入了新的字符（R++）（最右侧字符），而有了重复字符；
//则L++，直到没有重复字符；
class Solution {
    //利用滑动窗口，判断i,j区间内是否含有重复字符，有则i++
    public int lengthOfLongestSubstring(String s) {
        char[] cs = s.toCharArray();
        int n = cs.length;
        int ans = 0;
        if (n <= 1) return n;
        int L = 0;//起始位置
        int R = 0;
        HashSet<Character> windows = new HashSet<>();
        while (R < n) {
            while (windows.contains(cs[R])) {
                windows.remove(cs[L]);
                L++;
            }
            windows.add(cs[R]);
            ans = Math.max(ans, R - L + 1);
            R++;
        }
        return ans;
    }
}

1838. 最高频元素的频数

元素的 频数 是该元素在一个数组中出现的次数。

给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。

执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

示例 1：

输入：nums = [1,2,4], k = 5 输出：3 解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。 4 是数组中最高频元素，频数是 3 。

示例 2：

输入：nums = [1,4,8,13], k = 5 输出：2 解释：存在多种最优解决方案：

• 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
• 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
• 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。

示例 3：

输入：nums = [3,9,6], k = 2 输出：1  

提示：

1 <= nums.length <= 105

1 <= nums[i] <= 105

1 <= k <= 105

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 1;
        int i = 0;//初始位置
        int sum = 0;
        for (int j = 1; j < n;) {
        	//下面是一步求窗口内其余所有数与nums[j]差值之和
            //j为窗口的截至位置
            sum += (nums[j] - nums[j-1]) * (j - i);
            if (sum > k) {
                sum -= nums[j] - nums[i];
                i++;
            }
            ans = Math.max(ans, j - i + 1);
            j++;
        }
        return ans;
    }
}

• 思路如图示：

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

给定两个字符串 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 仅包含小写字母

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int len = p.length();
        int n = s.length();
        //全是小写字母，可以使用数组取代子字符串，简化操作
        int[] countS = new int[26];
        int[] countP = new int[26];
        for (char c : p.toCharArray()) {
            countP[c-'a']++;
        }
        //System.out.println(Arrays.toString(countP));
        int i = 0;//窗口开始位置
        for (int j = 0; j < n;) {
            countS[s.charAt(j) - 'a']++;
            if (j - i + 1 > len) {
                countS[s.charAt(i) - 'a']--;
                i++;
            }
            if (check(countS, countP)) {
                ans.add(i);
            }
            j++;//窗口结束位置
        }
        return ans;
    }
    boolean check(int[] count1, int[] count2) {
        for (int i = 0; i < 26; i++) {
            if (count1[i] != count2[i])
                return false;
        }
        return true;
    }
}

剑指 Offer II 017. 含有所有字符的最短字符串

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

 

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

示例 2：

输入：s = "a", t = "a" 输出："a"

示例 3：

输入：s = "a", t = "aa" 输出："" 解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：

1 <= s.length, t.length <= 105 s 和 t 由英文字母组成

class Solution {
    //统计词频 + 滑动窗口
    public String minWindow(String s, String t) {
        //A~z 对应ASCII 65 ~ 122;   122 - 65 + 1 = 58，所以开辟60足够用了。
        int[] count1 = new int[60];
        int[] count2 = new int[60];
        int n1 = s.length();
        int n2 = t.length();
        //维护一个最小长度，用于判断是否更新ans
        int minLength = s.length();
        String ans = "";
        //特判，s短于t,直接返回""
        if (n1 < n2) {
            return ans;
        }
        //统计出t中的词频
        for (char c : t.toCharArray()) {
            count2[c-'A']++;
        }
        //滑动窗口的起始位置分别为 i 、 j;
        int i = 0;//起始位置
        for (int j = 0; j < n1; j++) {
            //j对应字符进入窗口
            count1[s.charAt(j) - 'A']++;
            //如果当前的窗口已经包含了t中所有词频，则不断缩小窗口左边界
            while (Cover(count1, count2)) {
                //取等于号是WA出来的，对应样例 s = "a", t = "s";
                if (j - i + 1 <= minLength) {
                    minLength = j - i + 1;
                    ans = s.substring(i, i + minLength);
                }
                //左边界缩小，左边界对应的字符出窗
                count1[s.charAt(i) - 'A']--;
                i++;
            }
        }
        return ans;
    }
    //判断count1是否每一个元素都大于count2；
    boolean Cover(int[] count1, int[] count2) {
        for (int i = 0; i < 60; i++) {
            if (count1[i] < count2[i]) {
                return false;
            }
        }
        return true;
    }
}