滑动窗口找满足规则的区间问题

滑动窗口也为快慢指针。两个指针，fast指针在前面探路，slow指针负责在移动前做判断条件，然后再移动，两个指针覆盖的长度即为要找的元素空间。

常见的快慢指针题目：找满足条件的最长子串、删除排序的重复元素等。

滑动窗口算法框架

/* 滑动窗口算法框架 */
public void slidingWindow(String s, String t) {
    HashMap<Character, Integer> need = new HashMap<>();
    HashMap<Character, Integer> window = new HashMap<>();
    for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.length()) {
        char c = s.charAt(right);
        // 右移（增大）窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) valid++;
        }

        while (window needs shrink) {
            char d = s.charAt(left);
            // 左移（缩小）窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) valid--;
                window.put(d, window.getOrDefault(d, 0) - 1);
            }
        }
    }
}

2760. 最长奇偶子数组

Problem: 2760. 最长奇偶子数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 threshold 。

请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 (0 <= l <= r < nums.length) 且满足以下条件的 最长子数组 ：

nums[l] % 2 == 0
对于范围 [l, r - 1] 内的所有下标 i ，nums[i] % 2 != nums[i + 1] % 2
对于范围 [l, r] 内的所有下标 i ，nums[i] <= threshold

以整数形式返回满足题目要求的最长子数组的长度。

注意：子数组 是数组中的一个连续非空元素序列。

示例 1：

输入：nums = [3,2,5,4], threshold = 5
输出：3
解释：在这个示例中，我们选择从 l = 1 开始、到 r = 3 结束的子数组 => [2,5,4] ，满足上述条件。
因此，答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。

示例 2：

输入：nums = [1,2], threshold = 2
输出：1
解释：
在这个示例中，我们选择从 l = 1 开始、到 r = 1 结束的子数组 => [2] 。
该子数组满足上述全部条件。可以证明 1 是满足题目要求的最大长度。

示例 3：

输入：nums = [2,3,4,5], threshold = 4
输出：3
解释：
在这个示例中，我们选择从 l = 0 开始、到 r = 2 结束的子数组 => [2,3,4] 。 
该子数组满足上述全部条件。
因此，答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= threshold <= 100

思路

题目求区间长度，区间设定了规则，那么用双指针，结合if匹配规则找出最大的区间长度即可。
解题方法

滑动窗口，在条件里满足所有设定规则即可
复杂度

时间复杂度:

$O(n)$
空间复杂度:

$O(1)$

Code

class Solution {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int n = nums.length;
        int ans = Integer.MIN_VALUE;
        int left = 0, right = 0;
        while(right < n) {
            // 先满足 nums[l] % 2 == 0
            if (nums[left] % 2 != 0) {
                while(left < n && nums[left]  %2 != 0) {
                    left++;
                }
                right = left;
            } 
            if (right >= n) break;
            // 满足 nums[i] <= threshold
            if (left == right && nums[right] <= threshold) {
                ans = Math.max(ans, 1);
            }
            if(left == right && nums[right] > threshold) {
                right++;
                left = right;
                continue;
            }
            // 满足 nums[i] % 2 != nums[i + 1] % 2
            right++;
            if(right < n && (nums[right] % 2 != nums[right-1] % 2) && nums[right] <= threshold) {
                ans = Math.max(ans, right - left + 1);
            } else {
                left = right;
            }
        }
        return ans != Integer.MIN_VALUE ? ans: 0;
    }
}

632.最小区间

Problem: 632. 最小区间

你有 k 个 非递减排列 的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释： 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

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

提示：

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-10⁵ <= nums[i][j] <= 10⁵
nums[i] 按非递减顺序排列

思路

要求满足区间，可以用左右双指针去找；求每个列表都有一个数满足在区间内，可以用memo数组存储是否满足，当need满足列表长度时为满足所求，然后算出最小区间即可。
解题方法

思路在于把列表内的值都转化为hash映射，把列表都转化为index求是否所有的index都在区间内即可。
Code

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        // 整体思路：把列表里面的数都映射进hash表，然后用need数组need[nums.length]判断所求的区间是否都满足了每个列表都有一个数在区间内
        Map<Integer, List<Integer>> map = new HashMap<>();
        int size = nums.size();
        // 初始化满足的最小区间，最小值为所有列表里面的值的最小值，最大值为所有列表里面的值的最大值
        int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
        for(int i = 0; i < size; i++) {
            for(int x: nums.get(i)) {
                List<Integer> list = map.getOrDefault(x, new ArrayList<Integer>());
                list.add(i);
                map.put(x, list);
                minVal = Math.min(minVal, x);
                maxVal = Math.max(maxVal, x);
            }
        }

        // 滑动窗口从最新值开始滑动
        int left = minVal, right = minVal;
        // 记录是否列表
        int[] memo = new int[size];
        int need = 0;
        int bestL = minVal, bestR = maxVal;
        while(right <= maxVal) {
            // 如果right在map当中
            if(map.containsKey(right)) {
                for(int x: map.get(right)) {
                    // 记录区间满足了第x个列表
                    memo[x]++;
                    if (memo[x] == 1) need++;
                }
            } 
            // 当所有列表都满足了，记录区间大小，并缩小窗口
            while(need == size) {
                // 缩小区间
                if(right - left < bestR - bestL) {
                    bestL = left;
                    bestR = right;
                }
                if(map.containsKey(left)) {
                    for(int x: map.get(left)) {
                        if (memo[x] == 1) need--;
                        memo[x]--;
                    }
                }
                left++;
            }
            right++;
        }
        return new int[]{bestL, bestR};
    }
}

中间向两端扩散指针

中间向两端扩散，即左右指针分别朝左右两边扩散，常见为寻找回文子串，判断回文子串的重点为判断子串的长度是奇数还是偶数。

从给定位置寻找回文子串的算法：

// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
String palindrome(String s, int l, int r) {
    // 防止索引越界
    while (l >= 0 && r < s.length()
            && s.charAt(l) == s.charAt(r)) {
        // 双指针，向两边展开
        l--; r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substring(l + 1, r);
}

然后寻找给定字符串的最长回文子串：

String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++) {
        // 以 s[i] 为中心的最长回文子串
        String s1 = palindrome(s, i, i);
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        String s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}