スライディングウィンドウ入門

「連鎖・部分文字列・配列の問題は、まず双方向ポインタを考えよ。
双方向ポインタ三兄弟、それぞれに魅力あり。
速いポインタと遅いポインタは魔法使い、連結リスト操作に敵なし。
マージソートで中点を探し、連結リストの循環を判定。
左右ポインタが最も一般的、配列の両端から中央へ。
反転配列にはこれを頼れ、二分探索は弟分。
スライディングウィンドウは猛者、部分文字列問題はこれで決まり。
左右ポインタでウィンドウを滑らせ、一前一後で進め。
自称十年ドライバーも舗装されていない道では滑る。
アルゴリズム自体は簡単だが、バグが出たら昇天する。」

1. 最大連続する1の数

LeetCode 485 – 最大連続する1の数（簡単）詳細は元の問題を参照

2値配列 nums が与えられたとき、連続する 1 の最大の個数を計算せよ。

Pythonコード（改変版）

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        left = 0
        max_len = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                left = right + 1
            max_len = max(max_len, right - left + 1)
        return max_len

2. 部分配列の最大平均（長さk）

LeetCode 643 – 部分配列の最大平均 I（簡単）詳細は元の問題を参照

整数配列 nums と整数 k が与えられる。長さ k の連続部分配列の中で平均値が最大となるものを求め、その最大平均値を出力せよ。

Pythonコード（改変版）

class Solution:
    def findMaxAverage(self, nums, k):
        window_sum = sum(nums[:k])
        max_avg = window_sum / k
        for right in range(k, len(nums)):
            window_sum += nums[right] - nums[right - k]
            max_avg = max(max_avg, window_sum / k)
        return max_avg

3. 最長のハーモニー部分列

LeetCode 594 – 最長ハーモニー部分列（簡単）詳細は元の問題を参照

ハーモニー配列とは、配列内の最大値と最小値の差がちょうど 1 であるものをいう。整数配列 nums が与えられたとき、全ての部分列の中で最長のハーモニー部分列の長さを返せ。

Pythonコード（改変版）

class Solution:
    def findLHS(self, nums):
        if len(nums) <= 1:
            return 0
        nums.sort()
        left = 0
        ans = 0
        for right in range(len(nums)):
            while nums[right] - nums[left] > 1:
                left += 1
            if nums[right] - nums[left] == 1:
                ans = max(ans, right - left + 1)
        return ans

4. 長さ最小の部分配列（和がtarget以上）

LeetCode 209 – 長さ最小の部分配列（中程度）詳細は元の問題を参照

正の整数のみからなる配列 nums と正の整数 target が与えられる。合計が target 以上となる最短の連続部分配列 [numsl, numsl+1, ..., numsr-1, numsr] の長さを返せ。存在しない場合は 0 を返せ。

Pythonコード（改変版）

class Solution:
    def minSubArrayLen(self, target, nums):
        if sum(nums) < target:
            return 0
        left = 0
        total = 0
        min_len = float('inf')
        for right in range(len(nums)):
            total += nums[right]
            while total >= target:
                min_len = min(min_len, right - left + 1)
                total -= nums[left]
                left += 1
        return min_len

5. 最大連続する1の数 III（k回の0反転）

LeetCode 1004 – 最大連続する1の数 III（中程度）詳細は元の問題を参照

2値配列 nums と整数 k が与えられる。最大 k 個の 0 を 1 に反転できるとき、連続する 1 の最大の個数を返せ。

Pythonコード（改変版）

class Solution:
    def longestOnes(self, nums, k):
        left = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                k -= 1
            if k < 0:
                if nums[left] == 0:
                    k += 1
                left += 1
        return right - left + 1

6. 置換後の最長の繰り返し文字

LeetCode 424 – 置換後の最長の繰り返し文字 / LeetCode 2024 – 試験の最大混乱度（中程度）詳細は元の問題を参照

文字列 s と整数 k が与えられる。任意の文字を他の大文字に最大 k 回変更できるとき、同じ文字が連続する最長の部分文字列の長さを返せ。

考え方：

• k=0 なら最長連続部分文字列問題。
• k>0 なら k 個の文字を変更して連続させることを許容。
• ウィンドウ内の最頻出文字の出現回数を historyCharMax で保持（履歴最大）。
• ウィンドウの幅が historyCharMax + k を超えたら左端を縮める。

Pythonコード（改変版）

class Solution:
    def characterReplacement(self, s, k):
        from collections import Counter
        left = 0
        freq = Counter()
        max_freq = 0
        for right in range(len(s)):
            freq[s[right]] += 1
            max_freq = max(max_freq, freq[s[right]])
            if right - left + 1 > max_freq + k:
                freq[s[left]] -= 1
                left += 1
        return right - left + 1

7. 等しい部分文字列にするための最大コスト

LeetCode 1208 – 等しい部分文字列にするための最大コスト（中程度）詳細は元の問題を参照

同じ長さの文字列 s と t が与えられる。 s[i] を t[i] に変更するコストは |s[i] - t[i]|（ASCIIコードの差）。最大コスト maxCost 以内で s の部分文字列を t の対応部分に変更できる最長の部分文字列の長さを返せ。

Pythonコード（改変版）

class Solution:
    def equalSubstring(self, s, t, maxCost):
        left = 0
        ans = 0
        for right in range(len(s)):
            maxCost -= abs(ord(s[right]) - ord(t[right]))
            while maxCost < 0:
                maxCost += abs(ord(s[left]) - ord(t[left]))
                left += 1
            ans = max(ans, right - left + 1)
        return ans

8. 置換によるバランス文字列

LeetCode 1234 – 置換によるバランス文字列（中程度）詳細は元の問題を参照

文字 'Q', 'W', 'E', 'R' のみからなる長さ n の文字列がある。各文字がちょうど n/4 回出現するとき「バランス文字列」と呼ぶ。最小の置換回数でバランス文字列にするには？

Pythonコード（改変版）

class Solution:
    def balancedString(self, s):
        from collections import Counter
        n = len(s)
        target = n // 4
        count = Counter(s)
        # すでにバランスしているかチェック
        if all(count[c] <= target for c in 'QWER'):
            return 0

        left = 0
        min_replace = n
        for right in range(n):
            count[s[right]] -= 1
            # ウィンドウ外の文字数が全てtarget以下になるまで縮める
            while all(count[c] <= target for c in 'QWER'):
                min_replace = min(min_replace, right - left + 1)
                count[s[left]] += 1
                left += 1
        return min_replace

9. 固定長部分文字列中の母音の最大数

LeetCode 1456 – 固定長部分文字列中の母音の最大数（中程度）詳細は元の問題を参照

文字列 s と整数 k が与えられる。長さ k の連続部分文字列の中に含まれる母音（a, e, i, o, u）の最大数を返せ。

Pythonコード（改変版）

class Solution:
    def maxVowels(self, s, k):
        vowels = set('aeiou')
        window_count = 0
        max_count = 0
        for i in range(len(s)):
            if s[i] in vowels:
                window_count += 1
            if i >= k and s[i - k] in vowels:
                window_count -= 1
            if i >= k - 1:
                max_count = max(max_count, window_count)
        return max_count

10. 繰り返しDNA配列

LeetCode 187 – 繰り返しDNA配列（中程度）詳細は元の問題を参照

DNA配列を表す文字列 s が与えられる。長さ10の部分文字列で、2回以上出現するもの全てを返せ（順不同）。

Pythonコード（改変版）

class Solution:
    def findRepeatedDnaSequences(self, s):
        seen = set()
        repeated = set()
        for i in range(len(s) - 9):
            sub = s[i:i+10]
            if sub in seen:
                repeated.add(sub)
            else:
                seen.add(sub)
        return list(repeated)

11. 怒っている本屋のオーナー

LeetCode 1052 – 怒っている本屋のオーナー（中程度）詳細は元の問題を参照

本屋が n 分間営業している。各分 i に customers[i] 人の客が入店する。オーナーは grumpy[i] が 1 のとき不機嫌で、その分の客は満足しない。オーナーは一度だけ minutes 分間だけ不機嫌にならないようにできる。このとき最大何人の客を満足させられるか？

Pythonコード（改変版）

class Solution:
    def maxSatisfied(self, customers, grumpy, minutes):
        n = len(customers)
        # もともと満足している客数を計算し、grumpy=1のときの客数を0にリセット
        base = 0
        for i in range(n):
            if grumpy[i] == 0:
                base += customers[i]
                customers[i] = 0
        # customers配列は現在grumpy=1のときの客数だけが残っている
        # 長さminutesの部分配列の和の最大値を求める
        window_sum = sum(customers[:minutes])
        max_gain = window_sum
        for i in range(minutes, n):
            window_sum += customers[i] - customers[i - minutes]
            max_gain = max(max_gain, window_sum)
        return base + max_gain

12. フルーツバスケット

LeetCode 904 – フルーツバスケット（中程度）詳細は元の問題を参照

農場で果樹が一列に植えられている。配列 fruits で各木の果物の種類が示される。2種類の果物だけを集められるとき、連続して収穫できる最長の部分配列の長さを返せ。

Pythonコード（改変版）

class Solution:
    def totalFruit(self, fruits):
        from collections import defaultdict
        left = 0
        basket = defaultdict(int)
        max_len = 0
        for right in range(len(fruits)):
            basket[fruits[right]] += 1
            while len(basket) > 2:
                basket[fruits[left]] -= 1
                if basket[fruits[left]] == 0:
                    del basket[fruits[left]]
                left += 1
            max_len = max(max_len, right - left + 1)
        return max_len

13. 1つの要素を削除した後の最長の1のみの部分配列

LeetCode 1493 – 1つの要素を削除した後の最長の1のみの部分配列（中程度）詳細は元の問題を参照

2値配列 nums が与えられる。要素を1つだけ削除した後、連続する1のみからなる最長の非空の部分配列の長さを返せ。存在しない場合は 0。

Pythonコード（改変版）

class Solution:
    def longestSubarray(self, nums):
        left = 0
        zero_count = 0
        max_len = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            max_len = max(max_len, right - left)  # 1つ削除するので長さは right-left
        return max_len

14. 積がk未満の部分配列の個数

LeetCode 713 – 積がk未満の部分配列（中程度）詳細は元の問題を参照

整数配列 nums と整数 k が与えられる。全ての要素の積が厳密に k より小さい連続部分配列の個数を返せ。

Pythonコード（改変版）

class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
        if k <= 1:
            return 0
        left = 0
        prod = 1
        ans = 0
        for right in range(len(nums)):
            prod *= nums[right]
            while prod >= k:
                prod //= nums[left]
                left += 1
            ans += right - left + 1
        return ans

15. 最短かつ辞書順最小の美しい部分文字列

LeetCode 2904 – 最短かつ辞書順最小の美しい部分文字列（中程度）詳細は元の問題を参照

2値文字列 s と正の整数 k が与えられる。部分文字列中の 1 の個数がちょうど k のものを「美しい部分文字列」と呼ぶ。その中で最短かつ辞書順最小のものを返せ。存在しない場合は空文字列を返せ。

Pythonコード（改変版）

class Solution:
    def shortestBeautifulSubstring(self, s, k):
        if s.count('1') < k:
            return ''
        left = 0
        count = 0
        ans = s  # 初期値を最も長い文字列に設定
        for right in range(len(s)):
            if s[right] == '1':
                count += 1
            while count > k or s[left] == '0':
                if s[left] == '1':
                    count -= 1
                left += 1
            if count == k:
                cand = s[left:right+1]
                if len(cand) < len(ans) or (len(cand) == len(ans) and cand < ans):
                    ans = cand
        return ans

スライディングウィンドウ＋ハッシュテーブル

1. 重複要素の存在 II

LeetCode 219 – 重複要素の存在 II（簡単）詳細は元の問題を参照

整数配列 nums と整数 k が与えられる。 nums[i] == nums[j] かつ |i - j| <= k となる異なるインデックス i, j が存在すれば true、そうでなければ false を返せ。

Pythonコード（改変版）

class Solution:
    def containsNearbyDuplicate(self, nums, k):
        seen = set()
        left = 0
        for right in range(len(nums)):
            if nums[right] in seen:
                return True
            seen.add(nums[right])
            if len(seen) > k:
                seen.remove(nums[left])
                left += 1
        return False

2. 重複文字のない最長部分文字列

LeetCode 3 – 重複文字のない最長部分文字列（中程度）詳細は元の問題を参照

文字列 s が与えられる。重複する文字を含まない最長の部分文字列の長さを返せ。

Pythonコード（改変版）

class Solution:
    def lengthOfLongestSubstring(self, s):
        from collections import defaultdict
        left = 0
        max_len = 0
        freq = defaultdict(int)
        for right in range(len(s)):
            freq[s[right]] += 1
            while freq[s[right]] > 1:
                freq[s[left]] -= 1
                left += 1
            max_len = max(max_len, right - left + 1)
        return max_len

3. 文字列順列の存在チェック

LeetCode 567 – 文字列順列の存在（中程度）詳細は元の問題を参照

文字列 s1 と s2 が与えられる。 s2 に s1 の順列（文字の並び替え）が部分文字列として含まれれば true、そうでなければ false を返せ。

Pythonコード（改変版）

class Solution:
    def checkInclusion(self, s1, s2):
        from collections import Counter
        need = Counter(s1)
        window = Counter()
        left = 0
        match = 0
        for right in range(len(s2)):
            window[s2[right]] += 1
            if s2[right] in need and window[s2[right]] == need[s2[right]]:
                match += 1
            if right - left + 1 > len(s1):
                # 左端を移動
                if s2[left] in need and window[s2[left]] == need[s2[left]]:
                    match -= 1
                window[s2[left]] -= 1
                left += 1
            if match == len(need):
                return True
        return False

4. すべてのアナグラムの開始インデックス

LeetCode 438 – すべてのアナグラムの開始インデックス（中程度）詳細は元の問題を参照

文字列 s と p が与えられる。 s 中で p のアナグラム（文字の並び替え）となる部分文字列の開始インデックスを全て返せ。

Pythonコード（改変版）

class Solution:
    def findAnagrams(self, s, p):
        from collections import Counter
        need = Counter(p)
        window = Counter()
        left = 0
        match = 0
        result = []
        for right in range(len(s)):
            window[s[right]] += 1
            if s[right] in need and window[s[right]] == need[s[right]]:
                match += 1
            if right - left + 1 == len(p):
                if match == len(need):
                    result.append(left)
                # 左端を移動
                if s[left] in need and window[s[left]] == need[s[left]]:
                    match -= 1
                window[s[left]] -= 1
                left += 1
        return result

5. 最小カバー部分文字列

LeetCode 76 – 最小カバー部分文字列（難しい）詳細は元の問題を参照

文字列 s と t が与えられる。 s の中で t の全文字を含む最短の部分文字列を返せ（順序は問わない）。存在しない場合は空文字列を返せ。

Pythonコード（改変版）

class Solution:
    def minWindow(self, s, t):
        from collections import Counter
        need = Counter(t)
        window = Counter()
        left = 0
        match = 0
        start = 0
        min_len = float('inf')
        for right in range(len(s)):
            window[s[right]] += 1
            if s[right] in need and window[s[right]] == need[s[right]]:
                match += 1
            while match == len(need):
                if right - left + 1 < min_len:
                    start = left
                    min_len = right - left + 1
                # 左端を移動
                if s[left] in need and window[s[left]] == need[s[left]]:
                    match -= 1
                window[s[left]] -= 1
                left += 1
        return s[start:start + min_len] if min_len != float('inf') else ""

6. 部分配列削除の最大スコア（要素が全て異なる）

LeetCode 1695 – 部分配列削除の最大スコア（中程度）詳細は元の問題を参照

正整数配列 nums が与えられる。異なる要素のみからなる連続部分配列を1つ削除するとき、その部分配列の要素の和の最大値を返せ（削除部分は1つだけ）。

Pythonコード（改変版）

class Solution:
    def maximumUniqueSubarray(self, nums):
        from collections import defaultdict
        left = 0
        window = defaultdict(int)
        total = 0
        max_score = 0
        for right in range(len(nums)):
            window[nums[right]] += 1
            total += nums[right]
            while window[nums[right]] > 1:
                window[nums[left]] -= 1
                total -= nums[left]
                left += 1
            max_score = max(max_score, total)
        return max_score

7. 単語を連結した部分文字列

LeetCode 30 – 単語を連結した部分文字列（難しい）詳細は元の問題を参照

文字列 s と、同じ長さの単語からなる配列 words が与えられる。 words の全ての単語を任意の順で連結した部分文字列の開始インデックスを全て返せ。

Pythonコード（改変版）

class Solution:
    def findSubstring(self, s, words):
        from collections import Counter
        word_len = len(words[0])
        total_len = len(words) * word_len
        word_count = Counter(words)
        result = []
        for start in range(word_len):
            left = start
            window = Counter()
            match = 0
            for right in range(start, len(s) - word_len + 1, word_len):
                word = s[right:right + word_len]
                if word in word_count:
                    window[word] += 1
                    if window[word] == word_count[word]:
                        match += 1
                if right - left + word_len == total_len:
                    # ウィンドウがいっぱいになったらチェック
                    if match == len(word_count):
                        result.append(left)
                    # 左端を移動
                    left_word = s[left:left + word_len]
                    if left_word in word_count:
                        if window[left_word] == word_count[left_word]:
                            match -= 1
                        window[left_word] -= 1
                    left += word_len
        return result

変動長スライディングウィンドウ

1. 完全部分配列の個数

LeetCode 2799 – 完全部分配列の個数（中程度）詳細は元の問題を参照

正整数配列 nums が与えられる。部分配列に含まれる異なる要素の個数が、元の配列全体の異なる要素の個数と等しいとき「完全部分配列」と呼ぶ。完全部分配列の総数を返せ。

Pythonコード（改変版）

class Solution:
    def countCompleteSubarrays(self, nums):
        total_distinct = len(set(nums))
        left = 0
        freq = Counter()
        ans = 0
        for right in range(len(nums)):
            freq[nums[right]] += 1
            while len(freq) == total_distinct:
                freq[nums[left]] -= 1
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1
            # left は「短すぎる」部分配列の開始位置のインデックス
            # 実際には left 個の開始位置（0..left-1）が可能
            ans += left
        return ans

スライディングウィンドウ＋両端キュー

1. 差の絶対値が制限以内の最長連続部分配列

LeetCode 1438 – 差の絶対値が制限以内の最長連続部分配列（中程度）詳細は元の問題を参照

整数配列 nums と制限 limit が与えられる。部分配列内の任意の2要素の差の絶対値が limit 以下となる最長の連続部分配列の長さを返せ。

Pythonコード（改変版）

from collections import deque

class Solution:
    def longestSubarray(self, nums, limit):
        left = 0
        max_q = deque()  # 単調減少
        min_q = deque()  # 単調増加
        max_len = 0
        for right in range(len(nums)):
            # 最大値用キュー
            while max_q and nums[right] > nums[max_q[-1]]:
                max_q.pop()
            max_q.append(right)
            # 最小値用キュー
            while min_q and nums[right] < nums[min_q[-1]]:
                min_q.pop()
            min_q.append(right)

            # 差がlimitを超えたら左端を縮める
            while nums[max_q[0]] - nums[min_q[0]] > limit:
                if max_q[0] == left:
                    max_q.popleft()
                if min_q[0] == left:
                    min_q.popleft()
                left += 1
            max_len = max(max_len, right - left + 1)
        return max_len

まとめ

本記事ではスライディングウィンドウを基本から応用まで解説しました。問題のパターンを掴むことで、効率的な解法の選択が可能になります。面接対策としても役立つ問題を厳選しましたので、ぜひ実際にコーディングして習得してください。