FAAANGコーディング面接完全攻略：配列と文字列の核心パターン

FAANG（Facebook/Meta、Apple、Amazon、Netflix、Google）のコーディング面接では、配列と文字列の問題が全出題の40%以上を占めます。本記事では面接で頻出の6つの核心パターンを、動作するPythonコードと詳細な分析を交えて完全解説します。

1. Two Pointers パターン

概念と使用タイミング

Two Pointersパターンは、ソートされた配列や連結リストで2つのポインタを使い、線形時間で問題を解くテクニックです。

使用条件:

ソートされた配列で2要素の和・差を求める場合
配列の両端から条件を満たすペアを探す場合
重複除去やパーティショニングが必要な場合

核心アイデア: O(n^2)のブルートフォースをO(n)に削減できます。

問題 1: Two Sum II (LeetCode 167)

ソートされた配列で、合計がtargetになる2つの数のインデックスを見つけよ。

def twoSum(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []

# 例
# 入力: numbers = [2,7,11,15], target = 9
# 出力: [1,2]

時間計算量: O(n) — 各ポインタは最大n回移動 空間計算量: O(1) — 追加スペース不要

FAAANGのヒント: ソートされていない配列ならHashMapを使ったO(n)解法を先に提示し、ソート済み配列ではTwo Pointersが空間効率的であることを説明しましょう。

問題 2: 3Sum (LeetCode 15)

配列で合計が0になる3要素の組み合わせをすべて見つけよ（重複なし）。

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        # 重複をスキップ
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, len(nums) - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                # 重複をスキップ
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

# 例
# 入力: nums = [-1, 0, 1, 2, -1, -4]
# 出力: [[-1, -1, 2], [-1, 0, 1]]

時間計算量: O(n^2) — ソートO(n log n) + 二重ループO(n^2) 空間計算量: O(1) 〜 O(n)（ソートアルゴリズムによる）

FAAANGのヒント: Metaの面接で頻出です。重複処理のロジックを忘れないように注意しましょう。

問題 3: Container With Most Water (LeetCode 11)

高さ配列が与えられたとき、最も多くの水を入れられるコンテナの容量を求めよ。

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        current_water = width * min(height[left], height[right])
        max_water = max(max_water, current_water)

        # より低い側のポインタを移動（より高い壁を探す）
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

# 例
# 入力: height = [1,8,6,2,5,4,8,3,7]
# 出力: 49

時間計算量: O(n) 空間計算量: O(1)

なぜこの方法が最適か? より高い壁側を移動すると、幅は減り高さも減る（または同じ）ため、絶対に水量は増えません。

問題 4: Trapping Rain Water (LeetCode 42)

高難度問題。バーの間に溜まる雨水の総量を求めよ。

def trap(height: list[int]) -> int:
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0

    while left < right:
        if left_max <= right_max:
            left += 1
            left_max = max(left_max, height[left])
            # 現在位置で溜まる水 = 左側最大 - 現在高さ
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]

    return water

# 例
# 入力: height = [0,1,0,2,1,0,1,3,2,1,2,1]
# 出力: 6

時間計算量: O(n) 空間計算量: O(1) — プレフィックス最大配列不要

FAAANGのヒント: GoogleとAmazonの定番問題です。DP解法（O(n)スペース）も知っておき、Two Pointersがなぜより効率的かを説明できるようにしましょう。

2. Sliding Window パターン

概念

連続した部分配列/文字列で最適解を見つけるパターンです。ウィンドウをスライドさせながら全体を1回だけ走査します。

Fixed Window: ウィンドウサイズが固定 Variable Window: 条件によってウィンドウサイズが変化

問題 5: 最長の重複文字なし部分文字列 (LeetCode 3)

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

# HashMapを使った最適化版
def lengthOfLongestSubstringOptimized(s: str) -> int:
    char_index = {}
    left = 0
    max_length = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1

        char_index[char] = right
        max_length = max(max_length, right - left + 1)

    return max_length

# 例
# 入力: "abcabcbb"
# 出力: 3 ("abc")

時間計算量: O(n) 空間計算量: O(min(n, 文字セットサイズ))

問題 6: 最小ウィンドウ部分文字列 (LeetCode 76)

文字列sの中でtの全文字を含む最小ウィンドウを見つけよ。

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""

    need = Counter(t)
    missing = len(t)  # まだ含まれていない文字数

    best_start = 0
    best_end = float('inf')
    left = 0

    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        if missing == 0:
            # 左から不要な文字を取り除く
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1

            if right - left < best_end - best_start:
                best_start = left
                best_end = right

            # ウィンドウを縮小
            need[s[left]] += 1
            missing += 1
            left += 1

    if best_end == float('inf'):
        return ""
    return s[best_start:best_end + 1]

# 例
# 入力: s = "ADOBECODEBANC", t = "ABC"
# 出力: "BANC"

時間計算量: O(|s| + |t|) 空間計算量: O(|s| + |t|)

問題 7: スライディングウィンドウの最大値 (LeetCode 239)

サイズkのスライディングウィンドウの各位置での最大値を返せ。

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()  # 値の降順でインデックスを保持
    result = []

    for i, num in enumerate(nums):
        # ウィンドウ外に出たインデックスを削除
        if dq and dq[0] < i - k + 1:
            dq.popleft()

        # 現在の値より小さい要素は不要なので削除
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        # ウィンドウが完成したら結果を追加
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# 例
# 入力: nums = [1,3,-1,-3,5,3,6,7], k = 3
# 出力: [3,3,5,5,6,7]

時間計算量: O(n) — 各要素はdequeへの追加・削除が最大1回 空間計算量: O(k)

問題 8: バスケットに入れるフルーツ (LeetCode 904)

最大2種類のフルーツしか入れられないバスケットで連続して収穫できる最大数を求めよ。

from collections import defaultdict

def totalFruit(fruits: list[int]) -> int:
    basket = defaultdict(int)
    left = 0
    max_fruits = 0

    for right, fruit in enumerate(fruits):
        basket[fruit] += 1

        # 3種類以上になったら左ポインタを移動
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1

        max_fruits = max(max_fruits, right - left + 1)

    return max_fruits

# 例
# 入力: fruits = [1,2,1,2,3]
# 出力: 4 ([1,2,1,2])

時間計算量: O(n) 空間計算量: O(1) — 最大3種類のフルーツのみ保存

3. Binary Search パターン

概念

ソートされた配列でO(log n)時間で要素を探索します。標準形だけでなく様々な変形がFAANG面接に登場します。

標準 Binary Search テンプレート:

def binarySearch(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2  # オーバーフロー防止

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

問題 9: 回転ソート配列の検索 (LeetCode 33)

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # 左半分がソートされている場合
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 右半分がソートされている場合
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

# 例
# 入力: nums = [4,5,6,7,0,1,2], target = 0
# 出力: 4

時間計算量: O(log n) 空間計算量: O(1)

問題 10: 回転ソート配列の最小値 (LeetCode 153)

def findMin(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:
            left = mid + 1  # 最小値は右半分にある
        else:
            right = mid     # midが最小値の可能性あり

    return nums[left]

# 例
# 入力: nums = [3,4,5,1,2]
# 出力: 1

時間計算量: O(log n) 空間計算量: O(1)

問題 11: 2つのソート済み配列の中央値 (LeetCode 4) — 上級

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
    # nums1が短い配列になるよう保証
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    half_len = (m + n + 1) // 2

    left, right = 0, m

    while left <= right:
        i = (left + right) // 2   # nums1のパーティション
        j = half_len - i           # nums2のパーティション

        if i < m and nums1[i] < nums2[j - 1]:
            left = i + 1
        elif i > 0 and nums1[i - 1] > nums2[j]:
            right = i - 1
        else:
            if i == 0:
                max_left = nums2[j - 1]
            elif j == 0:
                max_left = nums1[i - 1]
            else:
                max_left = max(nums1[i - 1], nums2[j - 1])

            if (m + n) % 2 == 1:
                return float(max_left)

            if i == m:
                min_right = nums2[j]
            elif j == n:
                min_right = nums1[i]
            else:
                min_right = min(nums1[i], nums2[j])

            return (max_left + min_right) / 2.0

# 例
# 入力: nums1 = [1,3], nums2 = [2]
# 出力: 2.0

時間計算量: O(log(min(m, n))) 空間計算量: O(1)

問題 12: 2D行列の検索 (LeetCode 74)

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1

    while left <= right:
        mid = left + (right - left) // 2
        # 1Dインデックスを2D座標に変換
        mid_val = matrix[mid // cols][mid % cols]

        if mid_val == target:
            return True
        elif mid_val < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

# 例
# 入力: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# 出力: True

時間計算量: O(log(m*n)) 空間計算量: O(1)

4. Prefix Sum と HashMap パターン

概念

Prefix Sumは累積和を事前計算して区間和クエリをO(1)で処理します。HashMapと組み合わせると、特定条件を満たす区間を効率的に見つけられます。

問題 13: 合計がKの部分配列 (LeetCode 560)

合計がkの連続部分配列の数を求めよ。

from collections import defaultdict

def subarraySum(nums: list[int], k: int) -> int:
    prefix_sum_count = defaultdict(int)
    prefix_sum_count[0] = 1  # 空の配列のprefix sum = 0

    current_sum = 0
    count = 0

    for num in nums:
        current_sum += num
        # (current_sum - k)が以前に現れた回数を加算
        count += prefix_sum_count[current_sum - k]
        prefix_sum_count[current_sum] += 1

    return count

# 例
# 入力: nums = [1,1,1], k = 2
# 出力: 2

時間計算量: O(n) 空間計算量: O(n)

問題 14: 最長連続数列 (LeetCode 128)

ソートされていない配列で最長の連続数列の長さをO(n)で求めよ。

def longestConsecutive(nums: list[int]) -> int:
    num_set = set(nums)
    max_length = 0

    for num in num_set:
        # 数列の開始点のみ処理（num-1が存在しない場合）
        if num - 1 not in num_set:
            current = num
            length = 1

            while current + 1 in num_set:
                current += 1
                length += 1

            max_length = max(max_length, length)

    return max_length

# 例
# 入力: nums = [100,4,200,1,3,2]
# 出力: 4 ([1,2,3,4])

時間計算量: O(n) — 各要素は最大2回アクセス 空間計算量: O(n)

問題 15: アナグラムのグループ化 (LeetCode 49)

文字列の配列をアナグラムごとにグループ化せよ。

from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    anagram_map = defaultdict(list)

    for s in strs:
        key = tuple(sorted(s))
        anagram_map[key].append(s)

    return list(anagram_map.values())

# 文字カウントをキーとする最適化版
def groupAnagramsOptimized(strs: list[str]) -> list[list[str]]:
    anagram_map = defaultdict(list)

    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        anagram_map[tuple(count)].append(s)

    return list(anagram_map.values())

# 例
# 入力: strs = ["eat","tea","tan","ate","nat","bat"]
# 出力: [["bat"],["nat","tan"],["ate","eat","tea"]]

時間計算量: O(n _ k) — nは文字列数、kは最大文字列長 空間計算量: O(n _ k)

問題 16: 頻度上位K要素 (LeetCode 347)

from collections import Counter
import heapq

def topKFrequent(nums: list[int], k: int) -> list[int]:
    # 方法1: ヒープ O(n log k)
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

def topKFrequentBucketSort(nums: list[int], k: int) -> list[int]:
    # 方法2: バケットソート O(n)
    count = Counter(nums)

    bucket = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        bucket[freq].append(num)

    result = []
    for freq in range(len(bucket) - 1, 0, -1):
        for num in bucket[freq]:
            result.append(num)
            if len(result) == k:
                return result

    return result

# 例
# 入力: nums = [1,1,1,2,2,3], k = 2
# 出力: [1,2]

時間計算量: O(n) (バケットソート使用時) 空間計算量: O(n)

5. 企業別の出題傾向

Google

Googleの面接は配列と文字列操作に重点を置いています。

頻出: Two Sumの変形、文字列パーシング、2D配列探索
重視スキル: エッジケース処理、コードの明確性
例題: K種類以下の文字を持つ最長部分文字列、バルーンを割る矢の最小数

Meta（Facebook）

MetaはSliding WindowとTwo Pointerパターンを好みます。

頻出: 3Sum、Valid Palindrome II、Move Zeroes
重視スキル: 最適化理由の説明、コードの簡潔さ
例題: 積がK未満の部分配列、文字列の順列

Amazon

AmazonはHash TableとSortingベースの問題を好みます。

頻出: Two Sum、Group Anagrams、Top K Frequent
重視スキル: 実用的な解決策、リーダーシッププリンシパルとの関連付け
例題: K個の最近傍点、色の分類

Microsoft

MicrosoftはBinary Searchの変形と配列操作問題を多く出題します。

頻出: Find Peak Element、Search a 2D Matrix
重視スキル: エッジケース、バグのないコード
例題: Spiral Matrix、Rotate Image

6. 面接実践テクニック

問題解決フレームワーク（45分基準）

ステップ1 — 明確化（5分）

面接官に必ず確認すること:

入力の範囲とタイプ（負数可能? 重複あり?）
出力フォーマット（インデックス? 値? カウント?）
エッジケース（空配列、単一要素、全て同じ値）
最適化目標（時間 vs 空間）

ステップ2 — ブルートフォース（5分）

まずO(n^2)またはO(n^3)の単純な解法を説明します。これがベースラインになります。

ステップ3 — 最適化（10分）

パターン認識: Two Pointers? Sliding Window? Hash Map? 面接官とトレードオフを議論します。

ステップ4 — コーディング（15分）

クリーンにコーディングします。変数名は明確に、コメントは要点のみ:

def solve(nums, target):
    # Two Pointersの初期化
    left, right = 0, len(nums) - 1

    while left < right:
        # ... ロジック
        pass

ステップ5 — テスト（10分）

自分でテストケースを作り検証します:

通常ケース
エッジケース（空配列、長さ1）
最悪ケース（全て重複、逆順ソート）

エッジケースチェックリスト

配列・文字列問題で必ず確認:

空の入力 ([], "")
単一要素 ([5], "a")
全て同じ値 ([3,3,3,3])
既にソート済みの場合
逆順ソートの場合
整数オーバーフローの可能性
負数の有無

時間配分テーブル

フェーズ	時間	重点ポイント
明確化	5分	要件確認、質問
ブルートフォース	5分	ベースライン解法の提示
最適化	10分	パターン特定、計算量改善
コーディング	15分	クリーンでバグのない実装
テスト	10分	トレース、エッジケース確認

7. 練習問題クイズ

クイズ 1: Two Pointersでソート済み配列から重複を除去

ソート済み配列 nums = [0,0,1,1,1,2,2,3,3,4] からin-placeで重複を除去し、ユニークな要素数を返せ。追加スペースはO(1)のみ使用可。

答え: 5 (配列は [0,1,2,3,4,...] になる)

解説: Two Pointersを使います。遅いポインタ(slow)は次の書き込み位置を、速いポインタ(fast)は探索位置を指します。nums[fast] != nums[slow]の時、slowを増やして値をコピーします。

def removeDuplicates(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

クイズ 2: Sliding Windowで最大連続1の個数を求める

二値配列 nums = [1,1,0,0,1,1,1,0,1] で最大k=1個の0を1に変えられるとき、最長の連続1の部分配列の長さを求めよ。

答え: 6

解説: Variable Sliding Windowを使います。ウィンドウ内の0の個数がkを超えたら左ポインタを移動します。

def longestOnes(nums, k):
    left = 0
    zeros = 0
    max_len = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

クイズ 3: Binary Searchで境界値を探す

ソート済み配列 nums = [5,7,7,8,8,10] でtarget=8の開始インデックスと終了インデックスを求めよ。

答え: [3, 4]

解説: Binary Searchを2回実行します。1回目は最も左のインデックス（leftmost）、2回目は最も右のインデックス（rightmost）を探します。

def searchRange(nums, target):
    def findLeft(nums, target):
        left, right, idx = 0, len(nums) - 1, -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                idx = mid
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return idx

    def findRight(nums, target):
        left, right, idx = 0, len(nums) - 1, -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                idx = mid
                left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return idx

    return [findLeft(nums, target), findRight(nums, target)]

クイズ 4: Prefix Sumで合計がゼロの部分配列を数える

配列 [1, -1, 1, -1, 1] で合計が0の連続部分配列の数は?

答え: 4

解説: Prefix Sum + HashMapを使います。同じprefix sumが再度現れると、その間の区間の合計は0です。count += prefix_sum_count[current_sum - k]で計算します。

from collections import defaultdict
def subarraySum(nums, k=0):
    prefix_sum_count = defaultdict(int)
    prefix_sum_count[0] = 1
    current_sum = 0
    count = 0
    for num in nums:
        current_sum += num
        count += prefix_sum_count[current_sum - k]
        prefix_sum_count[current_sum] += 1
    return count
# 結果: 4

クイズ 5: 自分以外の積

配列 nums = [1,2,3,4] で各位置について自分以外の全要素の積を求めよ。除算禁止、O(n)時間、O(1)追加スペース。

答え: [24, 12, 8, 6]

解説: 左からの累積積（prefix product）と右からの累積積（suffix product）を利用します。出力配列自体を再利用してスペースを節約します。

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n

    # 左からの累積積
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # 右からの累積積を掛ける
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

まとめ

配列と文字列の問題はFAANG面接の根幹です。本記事で扱ったパターンを完全に習得すれば、ほとんどの問題をすばやく認識し、最適解法で取り組めるようになります。

次の学習ステップ:

LeetCodeで各パターンごとに20問ずつ解く
タイマーを使って45分以内に解く練習
コードレビュー: 他の人の解答と比較する
面接官役になって問題を作ってみる

次の記事ではツリーとグラフのパターンを解説します。