滑動視窗

# python
# LC 643 - Maximum Average Subarray I
# IDEA: add nums[i], evict nums[i - k] once the window is over-full, measure once it is k wide
# time = O(n), space = O(1)   (a counting map instead of a sum makes it O(k))
def findMaxAverage(nums, k):
    window_sum = 0
    best = float("-inf")
    for i in range(len(nums)):
        window_sum += nums[i]                 # add the newcomer
        if i >= k:
            window_sum -= nums[i - k]         # evict the element that fell out
        if i >= k - 1:                        # window is exactly k wide from here on
            best = max(best, window_sum)
    return best / k

// java
// LC 643 - Maximum Average Subarray I
// IDEA: add nums[i], evict nums[i - k] once the window is over-full, measure once it is k wide
// time = O(n), space = O(1)
public double findMaxAverage(int[] nums, int k) {
    int windowSum = 0;
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        windowSum += nums[i];                // add the newcomer
        if (i >= k) {
            windowSum -= nums[i - k];        // evict the element that fell out
        }
        if (i >= k - 1) {                    // exactly k wide from here on
            best = Math.max(best, windowSum);
        }
    }
    return (double) best / k;
}

for right in range(n):         # 1. expand: the window may now be invalid
    add(a[right])
    while not valid(window):   # 2. restore the invariant (may run 0 times)
        remove(a[left]); left += 1
    update_result(left, right)  # 3. the window is valid HERE, and only here

# python
# LC 1004 - Max Consecutive Ones III
# IDEA: grow right; while the window holds more than k zeros, shrink left; measure when valid
# time = O(n), space = O(1)
def longestOnes(nums, k):
    left = 0
    zeros = 0                                 # window state: zeros inside [left, right]
    best = 0
    for right in range(len(nums)):
        if nums[right] == 0:                  # 1. add
            zeros += 1
        while zeros > k:                      # 2. restore the invariant
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)    # 3. valid here, so measure here
    return best

// java
// LC 1004 - Max Consecutive Ones III
// IDEA: grow right; while the window holds more than k zeros, shrink left; measure when valid
// time = O(n), space = O(1)
public int longestOnes(int[] nums, int k) {
    int left = 0;
    int zeros = 0;                           // window state: zeros inside [left, right]
    int best = 0;
    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == 0) {
            zeros++;                         // 1. add
        }
        while (zeros > k) {                  // 2. restore the invariant
            if (nums[left] == 0) {
                zeros--;
            }
            left++;
        }
        best = Math.max(best, right - left + 1);  // 3. valid here
    }
    return best;
}

# python
# LC 3 - Longest Substring Without Repeating Characters
# IDEA: a set holds the window's characters; shrink from the left until s[right] is not in it
# time = O(n), space = O(min(n, charset))
def lengthOfLongestSubstring(s):
    in_window = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in in_window:          # invalid -> shrink until the duplicate is gone
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)    # valid here, so measure here
    return best

# python
# LC 3 - jump variant
# IDEA: last_seen[ch] = latest index of ch; on a repeat, jump left to last_seen[ch] + 1
# time = O(n), space = O(min(n, charset))
def lengthOfLongestSubstring_jump(s):
    last_seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen:
            left = max(left, last_seen[ch] + 1)   # max: a stale index must never pull left back
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

// java
// LC 3 - Longest Substring Without Repeating Characters
// IDEA: a set holds the window's characters; shrink from the left until s[right] is not in it
// time = O(n), space = O(min(n, charset))
public int lengthOfLongestSubstring(String s) {
    Set<Character> inWindow = new HashSet<>();
    int left = 0;
    int best = 0;
    for (int right = 0; right < s.length(); right++) {
        char ch = s.charAt(right);
        while (inWindow.contains(ch)) {      // invalid -> shrink until ch is gone
            inWindow.remove(s.charAt(left));
            left++;
        }
        inWindow.add(ch);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

s = "abba"            (jump variant)
right=0 'a'  left=0  window "a"   best=1
right=1 'b'  left=0  window "ab"  best=2
right=2 'b'  seen at 1 -> left=2  window "b"   best=2
right=3 'a'  seen at 0 -> left=max(2, 1)=2   window "ba"  best=2

# python
# LC 209 - Minimum Size Subarray Sum
# IDEA: grow right; while the sum still reaches target, record the length and shrink left
# time = O(n), space = O(1)
def minSubArrayLen(target, nums):
    left = 0
    window_sum = 0
    best = len(nums) + 1                      # sentinel: longer than any real window
    for right in range(len(nums)):
        window_sum += nums[right]
        while window_sum >= target:           # valid -> record, then try a shorter one
            best = min(best, right - left + 1)
            window_sum -= nums[left]
            left += 1
    return 0 if best == len(nums) + 1 else best

// java
// LC 209 - Minimum Size Subarray Sum
// IDEA: grow right; while the sum still reaches target, record the length and shrink left
// time = O(n), space = O(1)
public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int windowSum = 0;
    int best = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        windowSum += nums[right];
        while (windowSum >= target) {        // valid -> record, then try a shorter one
            best = Math.min(best, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }
    return best == Integer.MAX_VALUE ? 0 : best;
}

# python
# LC 209 - Minimum Size Subarray Sum (follow-up)
# IDEA: prefix sums are increasing; per start, binary-search the first end reaching target
# time = O(n log n), space = O(n)
from bisect import bisect_left

def minSubArrayLen_log(target, nums):
    n = len(nums)
    prefix = [0] * (n + 1)                    # prefix[i] = sum(nums[:i]), increasing
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = n + 1
    for left in range(n):
        # smallest right_end with prefix[right_end] - prefix[left] >= target
        right_end = bisect_left(prefix, prefix[left] + target)
        if right_end <= n:
            best = min(best, right_end - left)
    return 0 if best == n + 1 else best

# python
# LC 76 - Minimum Window Substring
# IDEA: need[c] = copies of c still owed (negative = surplus); missing = total owed;
#       when missing hits 0, drop surplus from the left, record, then break the window
# time = O(n + m), space = O(charset)
from collections import Counter

def minWindow(s, t):
    need = Counter(t)
    missing = len(t)
    best = ""
    left = 0
    for right, c in enumerate(s):
        if need[c] > 0:                       # c was owed -> one less missing
            missing -= 1
        need[c] -= 1
        if missing == 0:                      # window covers t
            while need[s[left]] < 0:          # drop surplus characters from the left
                need[s[left]] += 1
                left += 1
            if not best or right - left + 1 < len(best):
                best = s[left:right + 1]
            need[s[left]] += 1                # give up s[left]: the window owes it again
            missing += 1
            left += 1
    return best

// java
// LC 76 - Minimum Window Substring
// IDEA: count map of the window vs need; valid = distinct chars whose need is fully met;
//       while valid == need.size(), record and shrink
// time = O(n + m), space = O(charset)
public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    int left = 0;
    int valid = 0;                           // distinct chars whose need is fully met
    int start = 0;
    int minLen = Integer.MAX_VALUE;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        if (need.containsKey(c) && window.get(c).equals(need.get(c))) {
            valid++;
        }
        while (valid == need.size()) {       // valid -> record, then shrink
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
            char out = s.charAt(left);
            left++;
            if (need.containsKey(out) && window.get(out).equals(need.get(out))) {
                valid--;                     // about to drop below what t needs
            }
            window.put(out, window.get(out) - 1);
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

Exactly K = At Most K - At Most (K-1)

# python
# LC 992 - Subarrays with K Different Integers
# IDEA: at_most(k) counts subarrays with <= k distinct, adding right - left + 1 per right;
#       exactly k = at_most(k) - at_most(k - 1)
# time = O(n), space = O(k)
def subarraysWithKDistinct(nums, k):
    def at_most(k):
        if k == 0:
            return 0
        freq = {}
        left = 0
        count = 0
        for right in range(len(nums)):
            freq[nums[right]] = freq.get(nums[right], 0) + 1
            while len(freq) > k:              # shrink while more than k distinct
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1
            count += right - left + 1         # every suffix of [left, right] is valid
        return count

    return at_most(k) - at_most(k - 1)

// java
// LC 992 - Subarrays with K Different Integers
// IDEA: atMostK counts subarrays with <= k distinct, adding right - left + 1 per right;
//       exactly k = atMostK(k) - atMostK(k - 1)
// time = O(n), space = O(k)
public int subarraysWithKDistinct(int[] nums, int k) {
    return atMostK(nums, k) - atMostK(nums, k - 1);
}

private int atMostK(int[] nums, int k) {
    if (k == 0) {
        return 0;
    }
    Map<Integer, Integer> freq = new HashMap<>();
    int left = 0;
    int count = 0;
    for (int right = 0; right < nums.length; right++) {
        freq.put(nums[right], freq.getOrDefault(nums[right], 0) + 1);
        while (freq.size() > k) {            // shrink while more than k distinct
            freq.put(nums[left], freq.get(nums[left]) - 1);
            if (freq.get(nums[left]) == 0) {
                freq.remove(nums[left]);
            }
            left++;
        }
        count += right - left + 1;           // every suffix of [left, right] is valid
    }
    return count;
}

nums = [1, 2, 1, 2, 3], k = 2
at_most(2): ends at r=0..4 add 1, 2, 3, 4, 2   -> 12
at_most(1): ends at r=0..4 add 1, 1, 1, 1, 1   -> 5
exactly 2  = 12 - 5 = 7
  [1,2] [1,2,1] [1,2,1,2] [2,1] [2,1,2] [1,2] [2,3]

v is the sum    :  a + b == v   with a and b both in the window   (a == b needs two copies)
v is an addend  :  a and a + v  both in the window

# python
# LC 4067 Longest Subarray With Restricted Pair Sums
# IDEA : SLIDING WINDOW OVER VALUE COUNTS — test only the newcomer
# time = O(n * V), space = O(V)   (V = max(nums) <= 500)
class Solution(object):
    def maxSubarray(self, nums):
        n = len(nums)
        if n <= 2:                       # fewer than 3 elements can not form a triple
            return n
        max_val = max(nums)
        cnt = [0] * (max_val + 1)        # value -> copies inside the window
        left = 0
        best = 0
        for right in range(n):
            v = nums[right]
            # the window WITHOUT v is valid (loop invariant), so the only
            # triples that can appear are the ones that use v
            while self.joins_triple(cnt, v, max_val):
                cnt[nums[left]] -= 1     # removing can never create a triple
                left += 1
            cnt[v] += 1
            best = max(best, right - left + 1)
        return best

    def joins_triple(self, cnt, v, max_val):
        # 1) v is the sum : a + b == v, a <= b, both present (a == b needs two copies)
        for a in range(1, v // 2 + 1):
            b = v - a
            if a == b:
                if cnt[a] >= 2:
                    return True
            elif cnt[a] >= 1 and cnt[b] >= 1:
                return True
        # 2) v is an addend : a and a + v both present (a + v > a, so distinct indices)
        for a in range(1, max_val - v + 1):
            if cnt[a] >= 1 and cnt[a + v] >= 1:
                return True
        return False

// java
// LC 4067 - Longest Subarray With Restricted Pair Sums
// IDEA: Sliding window over value counts; the window before nums[r] joins is valid,
//       so only a triple that uses nums[r] can appear — test the newcomer, not the window
// time = O(n * V), space = O(V)   (V = max(nums) <= 500)
public int maxSubarray(int[] nums) {
    int n = nums.length;
    if (n <= 2) return n;                 // fewer than 3 elements can not form a triple
    int maxVal = 0;
    for (int x : nums) maxVal = Math.max(maxVal, x);
    int[] cnt = new int[maxVal + 1];      // value -> copies inside the window
    int l = 0, best = 0;
    for (int r = 0; r < n; r++) {
        int v = nums[r];
        // the window WITHOUT v is valid, so shrink until v completes no triple
        while (joinsTriple(cnt, v, maxVal)) {
            cnt[nums[l++]]--;             // removing can never create a triple
        }
        cnt[v]++;
        best = Math.max(best, r - l + 1);
    }
    return best;
}

private boolean joinsTriple(int[] cnt, int v, int maxVal) {
    // 1) v is the sum: a + b == v, a <= b, both present (a == b needs two copies)
    for (int a = 1; a <= v / 2; a++) {
        int b = v - a;
        if (a == b) {
            if (cnt[a] >= 2) return true;
        } else if (cnt[a] >= 1 && cnt[b] >= 1) {
            return true;
        }
    }
    // 2) v is an addend: a and a + v both present (a + v > a, so distinct indices)
    for (int a = 1; a + v <= maxVal; a++) {
        if (cnt[a] >= 1 && cnt[a + v] >= 1) return true;
    }
    return false;
}

nums = [2,3,5,3,2,1]

r=0  v=2  window {}       joins nothing                         -> [2]        len 1
r=1  v=3  window {2}      2+3=5 absent, no a+b=3                -> [2,3]      len 2
r=2  v=5  window {2,3}    sum: 2+3 = 5     -> drop 2 -> {3} ok  -> [3,5]      len 2
r=3  v=3  window {3,5}    3+3=6, 3+5=8 absent, no a+b=3         -> [3,5,3]    len 3  <- answer
r=4  v=2  window {3,5,3}  addend: 3 and 3+2=5 -> drop 3, still  -> drop 5 -> [3,2]  len 2
r=5  v=1  window {3,2}    addend: 2 and 2+1=3 -> drop 3         -> [2,1]      len 2

# Track character counts in window
window = {}
window[char] = window.get(char, 0) + 1

# Remove character from window
window[char] -= 1
if window[char] == 0:
    del window[char]

# Common validity checks
def is_valid_permutation(window, target):
    return window == target

def is_valid_distinct_k(window, k):
    return len(window) <= k

def is_valid_sum(current_sum, target):
    return current_sum >= target

# Maximum length problems
max_len = max(max_len, right - left + 1)

# Minimum length problems  
if is_valid:
    min_len = min(min_len, right - left + 1)

# Counting problems
count += right - left + 1  # All subarrays ending at 'right'