ゆめさくエンジニア研究所
2 つの指問題 08

小さい​順の​並びで​足して​目標に​なる 2 つ

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

問題

小さい順に並んだ整数の並び 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]

面接での聞かれ方

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

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

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

まず考える手順

段 1

まずは素直に、2 つの組を全部試す書き方を考えます。2 重の繰り返しで全部の組を足せば答えは見つかり、記憶も O(1) で済みます。ただ、長さが 10000 なら約 5000 万回の足し算になります。

段 2

問題 3 では、見た数を辞書に覚えて、繰り返しを 1 重にしました。この書き方は並び方に関係なく使え、時間は O(n) です。ただ、記憶を O(n) 使うので、この問題の決まりは守れません。

段 3

並んでいることを使います。左の指を先頭に、右の指を末尾に置き、2 つの数を足します。足した数が target より小さければ、和を大きくしたいので左の指を 1 つ右へ進めます。大きければ、和を小さくしたいので右の指を 1 つ左へ戻します。ちょうど同じになったところが答えです。

段 4

この寄せ方で答えを飛ばさない理由も、言えるようにしておきます。たとえば和が小さすぎたとき、左の数はいまの右の数と組んでも足りません。右の数はこれより大きくならないので、左の数はもう誰と組んでも答えになりません。だから、その数を候補から外してよいのです。

ここから​解答です。​先に​自分で​書いてから​読むと、​考え方が​残ります。

解答

Python

Python

def sorted_pair_sum(
    nums, target
):
    left = 0
    right = len(nums) - 1
    while left < right:
        a = nums[left]
        b = nums[right]
        total = a + b
        if total == target:
            return [left, right]
        if total < target:
            left += 1
        else:
            right -= 1
    return []

JavaScript

JavaScript

function sortedPairSum(
  nums, target
) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const a = nums[left];
    const b = nums[right];
    const total = a + b;
    if (total === target) {
      return [left, right];
    }
    if (total < target) {
      left++;
    } else {
      right--;
    }
  }
  return [];
}

左の指はいつも右の指より前にあるので、[left, right] の順に返せば小さい順になります。答えは必ず 1 組あるので、最後の return [] に来ることはありません。

計算量

  • 時間は O(n) です。1 回まわるごとに、どちらかの指が 1 つ内側へ進み、2 つの指が出会えば終わります
  • 使う記憶は O(1) です。指 2 つと、和を入れる置き場だけです
  • 問題 3 の辞書の書き方は、時間は同じ O(n) ですが、記憶が O(n) 要ります。並んでいるという手がかりのおかげで、記憶を減らせました

よくある間違い

  • 指の動かす向きを逆にする。和が小さいのに右の指を戻すと、和はもっと小さくなります。「大きくしたいなら小さい側を進める」と、言葉で確かめてから書きます
  • left <= right まで回す。 2 つの指が同じ位置に来ると、同じ数を 2 回使ってしまいます。止める条件は left < right です
  • 辞書の書き方をそのまま出して終える。正しく動きますが、記憶を使わない条件を満たしません。問題 3 との違いを聞かれている、と気づくことが大切です

面接での話し方の例

書き始める前に、方針を短く口に出します。

「並んでいない場合は辞書で O(n) の時間と O(n) の記憶でした。今回は小さい順なので、両端に指を置いて、和が小さければ左を進め、大きければ右を戻します。時間は O(n) のまま、記憶は O(1) にできます。」

書き終えたら、例を 1 つ手でたどって見せます。

「例 1 の [1, 3, 4, 8, 11] で目標 15 をたどります。1 と 11 で 12 は小さいので、左を進めます。3 と 11 で 14 もまだ小さいので、また左を進めます。4 と 11 で 15 になったので、[2, 4] を返します。」

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026年10月24日

コーディング面接問題の一覧へ戻る