滑動視窗

# Fixed Size Window Template
def fixed_window(s, k):
    window = {}
    result = []
    
    for i in range(len(s)):
        # Add current element to window
        window[s[i]] = window.get(s[i], 0) + 1
        
        # Remove element that's outside window
        if i >= k:
            left_char = s[i - k]
            window[left_char] -= 1
            if window[left_char] == 0:
                del window[left_char]
        
        # Process window when it reaches target size
        if i >= k - 1:
            # Check condition and update result
            if meets_condition(window):
                result.append(i - k + 1)
    
    return result

// Fixed Size Window Template - Java
public List<Integer> fixedWindow(String s, int k) {
    Map<Character, Integer> window = new HashMap<>();
    List<Integer> result = new ArrayList<>();
    
    for (int i = 0; i < s.length(); i++) {
        // Add current element
        char cur = s.charAt(i);
        window.put(cur, window.getOrDefault(cur, 0) + 1);
        
        // Remove element outside window
        if (i >= k) {
            char leftChar = s.charAt(i - k);
            window.put(leftChar, window.get(leftChar) - 1);
            if (window.get(leftChar) == 0) {
                window.remove(leftChar);
            }
        }
        
        // Process when window is full
        if (i >= k - 1 && meetsCondition(window)) {
            result.add(i - k + 1);
        }
    }
    return result;
}

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 Universal Template
def sliding_window(s, condition):
    # Initialize window state
    left = 0
    window_state = {}  # or Counter, set, etc.
    result = initialize_result()
    
    # Expand window with right pointer
    for right in range(len(s)):
        # Add current element to window
        update_window_state(s[right])
        
        # Contract window while invalid
        while not is_valid(window_state):
            # Remove leftmost element
            remove_from_window(s[left])
            left += 1
        
        # Update result with current valid window
        result = update_result(result, left, right)
    
    return result

// Java Universal Template  
public ResultType slidingWindow(String s) {
    // Initialize window state
    int left = 0;
    Map<Character, Integer> window = new HashMap<>();
    ResultType result = initializeResult();
    
    // Expand window with right pointer
    for (int right = 0; right < s.length(); right++) {
        char rightChar = s.charAt(right);
        window.put(rightChar, window.getOrDefault(rightChar, 0) + 1);
        
        // Contract window while invalid
        while (!isValid(window)) {
            char leftChar = s.charAt(left);
            window.put(leftChar, window.get(leftChar) - 1);
            if (window.get(leftChar) == 0) {
                window.remove(leftChar);
            }
            left++;
        }
        
        // Update result with current valid window
        result = updateResult(result, left, right);
    }
    
    return result;
}

// LC 3 - Longest Substring Without Repeating Characters
// IDEA: Sliding window with HashSet to track characters in window
// time = O(N), space = O(min(N, charset))
public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int l = 0, ans = 0;
    for (int r = 0; r < s.length(); r++) {
        while (set.contains(s.charAt(r))) {
            set.remove(s.charAt(l++));
        }
        set.add(s.charAt(r));
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

# LC 003 Longest Substring Without Repeating Characters
# IDEA : SLIDING WINDOW + DICT
#       -> use a hash table (d) record visited "element" (e.g. : a,b,c,...)
#          (but NOT sub-string)
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        d = {}
        # left pointer
        l = 0
        res = 0
        # right pointer
        for r in range(len(s)):
            """
            ### NOTE : we deal with "s[r] in d" case first 
            ### NOTE : if already visited, means "repeating"
            #      -> then we need to update left pointer (l)
            """
            if s[r] in d:
                """
                NOTE !!! this
                -> via max(l, d[s[r]] + 1) trick,
                   we can get the "latest" idx of duplicated s[r], and start from that one
                """
                l = max(l, d[s[r]] + 1)
            # if not visited yet, record the alphabet
            # and re-calculate the max length
            d[s[r]] = r
            res = max(res, r -l + 1)
        return res

// LC 209 - Minimum Size Subarray Sum
// IDEA: Sliding window — shrink left when sum >= target, record min length
// time = O(N), space = O(1)
public int minSubArrayLen(int target, int[] nums) {
    int l = 0, sum = 0, minLen = Integer.MAX_VALUE;
    for (int r = 0; r < nums.length; r++) {
        sum += nums[r];
        while (sum >= target) {
            minLen = Math.min(minLen, r - l + 1);
            sum -= nums[l++];
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

# LC 209 Minimum Size Subarray Sum
# IDEA : SLIDING WINDOW : start, end
class Solution:
    def minSubArrayLen(self, s, nums):
        if nums is None or len(nums) == 0:
            return 0

        n = len(nums)
        minLength = n + 1
        sum = 0
        j = 0
        for i in range(n):
            ### NOTE the while loop condition (j < n and sum < s)
            while j < n and sum < s:
                sum += nums[j]
                j += 1
            # NOTE : we need to check if sum >= s here
            if sum >= s:
                minLength = min(minLength, j - i)

            ### NOTE : we need to get min length of sub array
            #          so once it meats the condition (sum >= s)
            #          we should update the minLength (minLength = min(minLength, j - i))
            #          and move to next i and roll back _sum (_sum -= nums[i])
            sum -= nums[i]
            
        ### NOTE : if minLength == n + 1, means there is no such subarray, so return 0 instead
        if minLength == n + 1:
            return 0         
        return minLength

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:
            missing -= 1
        need[c] -= 1

        if missing == 0:              # valid window found
            # Shrink from left
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if not best or right - left + 1 < len(best):
                best = s[left:right+1]
            # Break window to search for next
            need[s[left]] += 1
            missing += 1
            left += 1

    return best

// LC 76 - Minimum Window Substring
// IDEA: Sliding window with frequency maps; shrink when window is valid
// time = O(N + M), space = O(N + M)
public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
    int l = 0, valid = 0, start = 0, minLen = Integer.MAX_VALUE;
    for (int r = 0; r < s.length(); r++) {
        char c = s.charAt(r);
        window.merge(c, 1, Integer::sum);
        if (need.containsKey(c) && window.get(c).equals(need.get(c))) valid++;
        while (valid == need.size()) {
            if (r - l + 1 < minLen) { minLen = r - l + 1; start = l; }
            char d = s.charAt(l++);
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) valid--;
                window.merge(d, -1, Integer::sum);
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

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

At Most K: All subarrays with ≤ K distinct/count
At Most (K-1): All subarrays with ≤ K-1 distinct/count

Difference: Only subarrays with EXACTLY K distinct/count

Array: [1, 2, 1, 2, 3]
K = 2 (exactly 2 distinct integers)

At Most 2 distinct:
[1], [1,2], [1,2,1], [1,2,1,2], [2], [2,1], [2,1,2], [1], [1,2], [2], [2,3], [3]
Count = 12

At Most 1 distinct:
[1], [2], [1], [2], [3]
Count = 5

Exactly 2 distinct = 12 - 5 = 7 ✓
[1,2], [1,2,1], [1,2,1,2], [2,1], [2,1,2], [1,2], [2,3]

# Subarray Counting Template
def count_subarrays(nums, condition):
    left = 0
    count = 0
    window_state = initialize_state()
    
    for right in range(len(nums)):
        # Add current element
        update_window_state(nums[right])
        
        # Shrink window while invalid
        while not is_valid(window_state):
            remove_from_window(nums[left])
            left += 1
        
        # Count valid subarrays ending at 'right'
        count += right - left + 1

    return count

# Python - LC 992 Subarrays with K Different Integers
def subarraysWithKDistinct(nums, k):
    """
    Count subarrays with exactly K distinct integers.

    Time: O(n)
    Space: O(k)

    Key: Use Exactly K = At Most K - At Most (K-1) transformation
    """
    def at_most_k_distinct(k):
        """Count subarrays with at most K distinct integers."""
        left = 0
        count = 0
        freq = {}

        for right in range(len(nums)):
            # Add right element
            freq[nums[right]] = freq.get(nums[right], 0) + 1

            # Shrink while > k distinct
            while len(freq) > k:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1

            # Count subarrays ending at right
            count += right - left + 1

        return count

    # Edge case
    if k == 0:
        return 0

    # Exactly K = At Most K - At Most (K-1)
    return at_most_k_distinct(k) - at_most_k_distinct(k - 1)

# Example:
# nums = [1,2,1,2,3], k = 2
# at_most_k(2) = 12
# at_most_k(1) = 5
# exactly_k(2) = 12 - 5 = 7 ✓

// Java - LC 992 Subarrays with K Different Integers
/**
 * time = O(N)
 * space = O(K)
 */
public int subarraysWithKDistinct(int[] nums, int k) {
    // Exactly K = At Most K - At Most (K-1)
    return atMostK(nums, k) - atMostK(nums, k - 1);
}

private int atMostK(int[] nums, int k) {
    if (k == 0) return 0;

    int left = 0;
    int count = 0;
    Map<Integer, Integer> freq = new HashMap<>();

    for (int right = 0; right < nums.length; right++) {
        // Add right element
        freq.put(nums[right], freq.getOrDefault(nums[right], 0) + 1);

        // Shrink while > k distinct
        while (freq.size() > k) {
            freq.put(nums[left], freq.get(nums[left]) - 1);
            if (freq.get(nums[left]) == 0) {
                freq.remove(nums[left]);
            }
            left++;
        }

        // Count subarrays ending at right
        count += right - left + 1;
    }

    return count;
}

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

# 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

// 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'