LeetCode（四）：滑动窗口技巧

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def max_sum_subarray(arr, k):
    """求长度为 k 的连续子数组的最大和。"""
    if len(arr) < k:
        return None

    window_sum = sum(arr[:k])     # 初始化第一个窗口的和
    best = window_sum

    for right in range(k, len(arr)):
        # 新进入窗口的元素是 arr[right]，离开的是 arr[right - k]
        window_sum += arr[right] - arr[right - k]
        best = max(best, window_sum)

    return best

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public int maxSumSubarray(int[] arr, int k) {
    if (arr.length < k) return Integer.MIN_VALUE;
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];  // 初始化窗口和
    int best = windowSum;
    for (int right = k; right < arr.length; right++) {
        windowSum += arr[right] - arr[right - k];      // 滑动窗口更新
        best = Math.max(best, windowSum);
    }
    return best;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def length_of_longest_substring(s):
    """LeetCode 3：无重复字符的最长子串。"""
    last_seen = {}        # 记录每个字符最近一次出现的位置
    left = 0              # 窗口左边界
    best = 0              # 最长子串长度

    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            # 如果当前字符在窗口内已存在，直接移动左边界
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)

    return best

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (last_seen.containsKey(c) && last_seen.get(c) >= left) {
            // 跳过重复字符的位置
            left = last_seen.get(c) + 1;
        }
        last_seen.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

from collections import Counter

def min_window(s, t):
    """LeetCode 76：覆盖 t 所有字符的最短子串。"""
    if not s or not t or len(s) < len(t):
        return ""

    need = Counter(t)  # 目标字符及其数量
    have = {}          # 当前窗口中目标字符的数量
    valid = 0          # 已满足条件的字符种类数
    left = 0           # 窗口左边界
    best_len = float("inf")  # 最短窗口长度
    best_start = 0     # 最短窗口起始位置

    for right, ch in enumerate(s):
        # 如果当前字符是目标字符，更新其计数
        if ch in need:
            have[ch] = have.get(ch, 0) + 1
            # 如果该字符的数量刚好达标，增加 valid
            if have[ch] == need[ch]:
                valid += 1

        # 当窗口合法时，尝试收缩左边界
        while valid == len(need):
            # 更新最短窗口信息
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_start = left

            # 移除左边界字符
            drop = s[left]
            left += 1
            if drop in need:
                # 如果移除后即将失衡，提前减少 valid
                if have[drop] == need[drop]:
                    valid -= 1
                have[drop] -= 1

    # 返回结果，若未找到合法窗口则返回空字符串
    return "" if best_len == float("inf") else s[best_start:best_start + best_len]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public String minWindow(String s, String t) {
    if (s.length() < t.length()) return "";
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);

    Map<Character, Integer> have = new HashMap<>();
    int valid = 0, left = 0;
    int bestLen = Integer.MAX_VALUE, bestStart = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (need.containsKey(c)) {
            have.merge(c, 1, Integer::sum);
            if (have.get(c).intValue() == need.get(c).intValue()) valid++;
        }
        // 窗口合法时尝试收缩
        while (valid == need.size()) {
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1;
                bestStart = left;
            }
            char d = s.charAt(left++);
            if (need.containsKey(d)) {
                if (have.get(d).intValue() == need.get(d).intValue()) valid--;
                have.merge(d, -1, Integer::sum);
            }
        }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def check_inclusion(s1, s2):
    """LeetCode 567：s2 是否包含 s1 的某个排列？"""
    n, m = len(s1), len(s2)
    if n > m:
        return False

    need = [0] * 26
    have = [0] * 26
    for c in s1:
        need[ord(c) - ord('a')] += 1
    for c in s2[:n]:
        have[ord(c) - ord('a')] += 1

    # 统计当前有多少个字符的频率匹配上了
    matches = sum(1 for i in range(26) if need[i] == have[i])

    for right in range(n, m):
        if matches == 26:
            return True

        r = ord(s2[right]) - ord('a')
        l = ord(s2[right - n]) - ord('a')

        # 新元素从右边进入窗口
        have[r] += 1
        if have[r] == need[r]:
            matches += 1
        elif have[r] == need[r] + 1:
            matches -= 1

        # 旧元素从左边移出窗口
        have[l] -= 1
        if have[l] == need[l]:
            matches += 1
        elif have[l] == need[l] - 1:
            matches -= 1

    return matches == 26

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public boolean checkInclusion(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    if (n > m) return false;
    int[] need = new int[26], have = new int[26];
    for (int i = 0; i < n; i++) {
        need[s1.charAt(i) - 'a']++;
        have[s2.charAt(i) - 'a']++;
    }
    int matches = 0;
    for (int i = 0; i < 26; i++) if (need[i] == have[i]) matches++;
    for (int right = n; right < m; right++) {
        if (matches == 26) return true;
        int r = s2.charAt(right) - 'a';
        int l = s2.charAt(right - n) - 'a';
        have[r]++;
        if (have[r] == need[r]) matches++;
        else if (have[r] == need[r] + 1) matches--;
        have[l]--;
        if (have[l] == need[l]) matches++;
        else if (have[l] == need[l] - 1) matches--;
    }
    return matches == 26;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

from collections import deque

def max_sliding_window(nums, k):
    """LeetCode 239：每个长度为 k 的窗口的最大值。"""
    dq = deque()      # 存储下标；对应的值在 nums 中严格递减
    out = []

    for i, x in enumerate(nums):
        # 1. 踢掉队尾所有比 x 小的元素——它们不可能再成为最大值
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)

        # 2. 如果队首已经滑出窗口，直接移除
        if dq[0] <= i - k:
            dq.popleft()

        # 3. 窗口形成后，队首就是当前窗口的最大值
        if i >= k - 1:
            out.append(nums[dq[0]])

    return out

1
2
3
4
5
6
7
8

def fixed_window(arr, k):
    state = init_state(arr[:k])           # 例如和、频次表
    best = report(state)
    for right in range(k, len(arr)):
        state = add(state, arr[right])
        state = remove(state, arr[right - k])
        best = better(best, report(state))
    return best

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def longest_valid(arr):
    left = 0
    state = empty_state()
    best = 0
    for right, x in enumerate(arr):
        state = add(state, x)
        while not is_valid(state):
            state = remove(state, arr[left])
            left += 1
        best = max(best, right - left + 1)
    return best

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def shortest_valid(arr):
    left = 0
    state = empty_state()
    best = float("inf")
    for right, x in enumerate(arr):
        state = add(state, x)
        while is_valid(state):
            best = min(best, right - left + 1)
            state = remove(state, arr[left])
            left += 1
    return best if best != float("inf") else 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# C 风格
right = 0
while right < len(arr):
    add(arr[right])
    while bad(): remove(arr[left]); left += 1
    best = max(best, right - left + 1)
    right += 1

# Pythonic
left = 0
for right, x in enumerate(arr):
    add(x)
    while bad():
        remove(arr[left]); left += 1
    best = max(best, right - left + 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from collections import Counter

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    cnt = Counter()
    left = best = 0
    for right, c in enumerate(s):
        cnt[c] += 1
        while len(cnt) > k:
            cnt[s[left]] -= 1
            if cnt[s[left]] == 0:
                del cnt[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best