技巧

滑动窗口/尺取法

滑动窗口模板伪代码：

public int slidingWindowExample(char[] arr) {
	int n = arr.length;  // 取数组或字符串长度
	int p = 0, q = 0;  // 双指针，表示当前遍历区间为[p, q]
	Record rec = new Record(arr);  // 用于统计结果是否有效
	int res = 0;  // 保存满足要求的最大结果
	while (q < n) {  // 当右指针没有到结尾
		rec.updateRight(q);  // 更新右指针处的统计
		// 如果不满足要求，就需要一直移动左指针，直到找到一个符合题意的区间
		while (rec.isNotMatch(p, q)) {
			rec.updateLeft(p);  // 更新左指针处的统计
			p++;  // 移动左指针
		}
		res = Math.max(res, q - p + 1);  // 更新结果
		q++;  // 移动右指针
	}
	return res;
}

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：

1. 定义两个指针：左指针p 和右指针q 分别指向区间的开头和结尾，注意是闭区间；定义 rec 用来对当前遍历区间 [p, q] 进行统计；
2. 第一重 while 循环是为了判断右指针的位置是否超出了数组边界；当右指针每次到了新位置，需要更新右指针处的统计；
3. 第二重 while 循环是让左指针向右移动到 [p, q] 区间符合题意的位置；当左指针每次移动到新位置前，需要更新左指针处的统计；
4. 在第二重 while 循环之后，成功找到了一个符合题意的 [p, q] 区间，题目要求最大的区间长度，因此更新 res 为 max(res, 当前区间的长度) 。
5. 右指针每次向右移动一步，开始探索新的区间。

题目示例

3. 无重复字符的最长子串 - 力扣（LeetCode）

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int p = 0, q = 0;
        char[] cs = s.toCharArray();
        Map<Character, Integer> cm = new HashMap<>();
        int res = 0;
        while (q < n) {
            cm.put(cs[q], cm.getOrDefault(cs[q], 0) + 1);
            while (cm.getOrDefault(cs[p], 0) > 1 || cm.getOrDefault(cs[q], 0) > 1) {
                cm.put(cs[p], cm.getOrDefault(cs[p], 0) - 1);
                p++;
            }
            res = Math.max(res, q - p + 1);
            q++;
        }
        return res;
    }
}