滑动窗口技巧

int left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

/* 滑动窗口算法框架 */
import java.util.HashMap;

public class Main {

    void slidingWindow(String s) {
        HashMap<Character, Integer> window = new HashMap<>();
        
        int left = 0, right = 0;
        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 增大窗口
            right++;
            // 进行窗口内数据的一系列更新
            // 比如：window.put(c, window.getOrDefault(c, 0) + 1);
            ...

            /*** debug 输出的位置 ***/
            // 注意在最终的解法代码中不要 print
            // 因为 IO 操作很耗时，可能导致超时
            System.out.println("window: [" + left + ", " + right + ")");
            /********************/
            
            // 判断左侧窗口是否要收缩
            while (/* window needs shrink */) {
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 缩小窗口
                left++;
                // 进行窗口内数据的一系列更新
                // 比如：window.put(d, window.get(d) - 1);
                ...
            }
        }
    }
    
    public static void main(String[] args) {
        Main m = new Main();
        m.slidingWindow("your_test_string_here");
    }
}

for (int i = 0; i < s.size(); i++)
    for (int j = i + 1; j < s.size(); j++)
        if s[i:j] 包含 t 的所有字母:
            更新答案

unordered_map<char, int> need, window;
for (char c : t) need[c]++;

int left = 0, right = 0;
int valid = 0; 
while (right < s.size()) {
    // 开始滑动
}

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    // 记录最小覆盖子串的起始索引及长度
    int start = 0, len = INT_MAX;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 扩大窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (valid == need.size()) {
            // 在这里更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            char d = s[left];
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }                    
        }
    }
    // 返回最小覆盖子串
    return len == INT_MAX ? "" : s.substr(start, len);
}

// 判断 s 中是否存在 t 的排列
bool checkInclusion(string t, string s) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }

        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 在这里判断是否找到了合法的子串
            if (valid == need.size())
                return true;
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    // 未找到符合条件的子串
    return false;
}

vector<int> findAnagrams(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    vector<int> res; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) 
                valid++;
        }
        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid == need.size())
                res.push_back(left);
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> win = new HashMap<>();
        int left = 0, right = 0;
        int res = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            win.put(c, win.getOrDefault(c, 0) + 1);
            right++;
            while (win.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                if(win.containsKey(d)) 
                    win.put(d, win.getOrDefault(d, 0) - 1);
            }
           
            res = Math.max(res, right - left);
        }
        return res;
    }
}

int[] maxSlidingWindow(int[] nums, int k);

class Queue {
    // enqueue 操作，在队尾加入元素 n
    void push(int n);
    // dequeue 操作，删除队头元素
    void pop();
}

class MonotonicQueue {
    // 在队尾添加元素 n
    void push(int n);
    // 返回当前队列中的最大值
    int max();
    // 队头元素如果是 n，删除它
    void pop(int n);
}

int[] maxSlidingWindow(int[] nums, int k) {
    MonotonicQueue window = new MonotonicQueue();
    List<Integer> res = new ArrayList<>();
    
    for (int i = 0; i < nums.length; i++) {
        if (i < k - 1) {
            //先把窗口的前 k - 1 填满
            window.push(nums[i]);
        } else {
            // 窗口开始向前滑动
            // 移入新元素
            window.push(nums[i]);
            // 将当前窗口中的最大元素记入结果
            res.add(window.max());
            // 移出最后的元素
            window.pop(nums[i - k + 1]);
        }
    }
    // 将 List 类型转化成 int[] 数组作为返回值
    int[] arr = new int[res.size()];
    for (int i = 0; i < res.size(); i++) {
        arr[i] = res.get(i);
    }
    return arr;
}

class MonotonicQueue {
// 双链表，支持头部和尾部增删元素
// 维护其中的元素自尾部到头部单调递增
private LinkedList<Integer> maxq = new LinkedList<>();

// 在尾部添加一个元素 n，维护 maxq 的单调性质
public void push(int n) {
    // 将前面小于自己的元素都删除
    while (!maxq.isEmpty() && maxq.getLast() < n) {
        maxq.pollLast();
    }
    maxq.addLast(n);
}

public int max() {
    // 队头的元素肯定是最大的
    return maxq.getFirst();
}

public void pop(int n) {
    if (n == maxq.getFirst()) {
        maxq.pollFirst();
    }
}

/* 单调队列的实现 */
class MonotonicQueue {
    LinkedList<Integer> maxq = new LinkedList<>();
    public void push(int n) {
        // 将小于 n 的元素全部删除
        while (!maxq.isEmpty() && maxq.getLast() < n) {
            maxq.pollLast();
        }
        // 然后将 n 加入尾部
        maxq.addLast(n);
    }
    
    public int max() {
        return maxq.getFirst();
    }
    
    public void pop(int n) {
        if (n == maxq.getFirst()) {
            maxq.pollFirst();
        }
    }
}

/* 解题函数的实现 */
int[] maxSlidingWindow(int[] nums, int k) {
    MonotonicQueue window = new MonotonicQueue();
    List<Integer> res = new ArrayList<>();
    
    for (int i = 0; i < nums.length; i++) {
        if (i < k - 1) {
            //先填满窗口的前 k - 1
            window.push(nums[i]);
        } else {
            // 窗口向前滑动，加入新数字
            window.push(nums[i]);
            // 记录当前窗口的最大值
            res.add(window.max());
            // 移出旧数字
            window.pop(nums[i - k + 1]);
        }
    }
    // 需要转成 int[] 数组再返回
    int[] arr = new int[res.size()];
    for (int i = 0; i < res.size(); i++) {
        arr[i] = res.get(i);
    }
    return arr;
}

/* 单调队列的通用实现，可以高效维护最大值和最小值 */
class MonotonicQueue<E extends Comparable<E>> {

    // 标准队列 API，向队尾加入元素
    public void push(E elem);

    // 标准队列 API，从队头弹出元素，符合先进先出的顺序
    public E pop();

    // 标准队列 API，返回队列中的元素个数
    public int size();

    // 单调队列特有 API，O(1) 时间计算队列中元素的最大值
    public E max();

    // 单调队列特有 API，O(1) 时间计算队列中元素的最小值
    public E min();
}

/**
 *用于记录链表的大小
 */
transient int size = 0;
/**
 * 链表第一个节点的引用
 */
transient Node<E> first;
/**
 * 链表最后一个节点的引用
 */
transient Node<E> last;
/**
 * 私有的静态内部类，用于描述双向链表的节点
 */
private static class Node<E> {
    E item; // 节点的值，也就是List中的元素
    Node<E> next; // 直接前驱节点
    Node<E> prev; // 直接后继节点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
/**
 * 向指定索引处插入元素
 */
 public void add(int index, E element) {
     // 检查index是否合法，index >= 0 && index <= size
     checkPositionIndex(index);
     if (index == size)
         linkLast(element); // 追加到链表尾部
     else
         linkBefore(element, node(index)); 
 }
 /**
 * 将元素添加到链表尾部。
 */
void linkLast(E e) {
    final Node<E> l = last; // 记录链表的最后一个节点
    // 创建新节点，设置其前驱节点为l，值为e，后继节点为null
    final Node<E> newNode = new Node<>(l, e, null); 
    last = newNode; // last指向新创建的这个节点
    /*如果l指向的是null（注意，此时l和last指向的已经不是同一个对象了），
      说明newNode既是第一个节点，又是最后一个节点，也就是说newNode是链表中唯一的一个节点*/
    if (l == null) 
        first = newNode;
    else
        l.next = newNode; // l的后继节点设置为newNode
    size++;
    modCount++;
}
 /**
  * 返回指定索引处的节点
  */
 Node<E> node(int index) {
     // assert isElementIndex(index);
	 // 可以看出这里是通过遍历的方式查找index处的节点。
	 // 为了减少遍历的节点个数，提高查找效率，这里判断了index是在链表的前半段还是后半段，
	 // 从而实现从半个链表中查找index处的节点
     if (index < (size >> 1)) {
         Node<E> x = first;
         for (int i = 0; i < index; i++)
             x = x.next;
         return x;
     } else {
         Node<E> x = last;
         for (int i = size - 1; i > index; i--)
             x = x.prev;
         return x;
     }
 }
 /**
  * 将元素包装成链表节点插入到指定节点的前面
  */
 void linkBefore(E e, Node<E> succ) {
     // assert succ != null;
     final Node<E> pred = succ.prev; // 记录succ的前驱节点
     final Node<E> newNode = new Node<>(pred, e, succ); // 创建新节点newNode，值为e
     succ.prev = newNode; // 将succ的前驱节点设置为newNode
     if (pred == null) // 此时链表的第一个节点是newNode
         first = newNode;
     else
         pred.next = newNode;
     size++;
     modCount++;
 }
 /**
  * 获取指定索引处的元素
  */
 public E get(int index) {
     // 索引合法性检查。index >= 0 && index < size
     checkElementIndex(index);
     return node(index).item; // 通过遍历查找节点并获取元素
 }
 /**
  * 替换列表中指定位置的元素，返回被替换的元素。
  * 核心代码依旧是通过遍历查找节点
  */
 public E set(int index, E element) {
     checkElementIndex(index);
     Node<E> x = node(index);
     E oldVal = x.item;
     x.item = element;
     return oldVal;
 }
 /**
  * 移除列表中指定位置的元素
  */
 public E remove(int index) {
     checkElementIndex(index);
     // 先遍历查找index处的节点，再调用unlink方法
     return unlink(node(index));
 }
 /**
  * 从链表中删除一个节点
  */
 E unlink(Node<E> x) {
     // assert x != null;
     final E element = x.item; // 记录被删除节点的元素
     final Node<E> next = x.next; // 记录被删除节点的后继节点
     final Node<E> prev = x.prev; // 记录被删除节点的前驱节点

     if (prev == null) { // 被删除节点的前驱节点为null，说明被删除节点是链表的第一个节点
         first = next; // 此时链表的第一个节点是被删除节点的后继节点
     } else {
         prev.next = next; 
         x.prev = null; 
     }

     if (next == null) { // 被删除节点的后继节点为null，说明被删除节点是链表的最后一个节点
         last = prev; // 此时链表的最后一个节点是被删除节点的前驱节点
     } else {
         next.prev = prev;
         x.next = null;
     }

     x.item = null; // 彻底释放被删除节点
     size--; // 表长减一
     modCount++;
     return element;
 }