ソート済み配列の Two Sum をツーポインタで解く - LeetCode 167

小さい順に並んだ整数の並びから、足すと目標になる 2 つの位置を返します。両端に指を置いて内側へ寄せ、余分な記憶を使わずに探す練習です。

海外で定番の問題リスト 4 本のうち 2 本に入っています (NeetCode 150、LeetCode Top Interview 150)

問題

小さい順に並んだ整数の並び nums と、整数 target を受け取ります。nums の中から足すと target になる 2 つの数を選び、その位置 (0 から数えた番号) を小さい順に並べて返す関数を書いてください。

  • nums は小さい順に並んでいます。同じ値が続くこともあります
  • 答えになる組は、ちょうど 1 組だけあるものとします。同じ位置の数を 2 回使うことはできません
  • nums の長さは 2 以上 10000 以下、値はどれも絶対値が 10 億以下です
  • 足した数を覚えるための辞書や新しい並びを使わず、決まった数の置き場だけで解いてください

入力と出力の例

例 1

入力

nums = [1, 3, 4, 8, 11]
target = 15

出力

[2, 4]

例 2

負の数も入ります。

入力

nums = [-6, -2, 0, 5, 9]
target = 7

出力

[1, 4]

例 3

同じ値でも、位置が違えば別の数として使えます。

入力

nums = [2, 7, 7, 13]
target = 14

出力

[1, 2]

図で見る

例 1 で、解き方がどう動くか。押すと大きく開きます。

面接での聞かれ方

面接では、並んでいない並びで「足して目標になる 2 つの位置」を探す Two Sum を解いたあとに、続きとして出されることがよくあります。

  • 「では、配列が小さい順に並んでいたらどうしますか?」
  • 「追加のメモリを使わずに解けますか?」と、記憶の使い方を条件に足されます
  • 「並んでいることを、どう使いましたか?」と、考えの筋を聞かれることもあります

Two Sum の辞書の書き方をそのまま出しても正しく動きます。ただ、ここで聞かれているのは「並んでいる」という手がかりの使い方です。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

  1. ヒント 2

  2. ヒント 3

  3. ヒント 4答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

main.py
def sorted_pair_sum(nums: list[int], target: int) -> list[int]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(sorted_pair_sum([1, 3, 4, 8, 11], 15))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します