ソート済み配列の Two Sum を ツーポインタで解く - LeetCode 167
小さい
海外で定番の問題リスト 4 本のうち 2 本に入っています (NeetCode 150、LeetCode Top Interview 150)
問題
小さいnums と、target をnums のtarget に
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 で、
面接での聞かれ方
面接では、
- 「では、
配列が 小さい 順に 並んでいたら どうしますか?」 - 「追加の
メモリを 使わずに 解けますか?」と、 記憶の 使い方を 条件に 足されます - 「並んでいる
ことを、 どう 使いましたか?」と、 考えの 筋を 聞かれる こともあります
Two Sum の
ヒント
まだ開いていません
付箋は 4 枚。下の段ほど答えに近づきます
ヒント 2
ヒント 3
ヒント 4答えに近い
アルゴリズムのチートシートの「配列と文字列」に、
関わる学び
配列と
まず 考える手順
段 1
まずは
段 2
並んでいない Two Sum では、
段 3
並んでいるtarget より
段 4
この
解答
Python
Python
def sorted_pair_sum(
nums: list[int],
target: int,
) -> list[int]:
left = 0
right = len(nums) - 1
while left < right:
total = nums[left] + nums[right]
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 total =
nums[left] + nums[right];
if (total === target) {
return [left, right];
}
if (total < target) {
left++;
} else {
right--;
}
}
return [];
}Go
Go
func sortedPairSum(
nums []int, target int,
) []int {
left := 0
right := len(nums) - 1
for left < right {
total := nums[left] + nums[right]
if total == target {
return []int{left, right}
}
if total < target {
left++
} else {
right--
}
}
return []int{}
}左の[left, right] のreturn [] に
計算量
- 時間は O(n) です。
1 回まわる ごとに、 どちらかの 指が 1 つ内側へ 進み、 2 つの 指が 出会えば 終わります - 使う
記憶は O(1) です。 指 2 つと、 和を 入れる 置き場だけです - Two Sum の
辞書の 書き方は、 時間は 同じ O(n) ですが、 記憶が O(n) 要ります。 並んでいるという 手が かりの おかげで、 記憶を 減らせました
よく ある間違い
- 指の
動かす 向きを 逆にする。 和が 小さいのに 右の 指を 戻すと、 和は もっと 小さくなります。 「大きくしたいなら 小さい 側を 進める」と、 言葉で 確かめてから書きます left <= rightまで回す。 2 つの指が 同じ 位置に 来ると、 同じ数を 2 回使ってしまいます。 止める 条件は left < rightです- 辞書の
書き方を そのまま 出して終える。 正しく 動きますが、 記憶を 使わない 条件を 満たしません。 並んでいない Two Sum との 違いを 聞かれている、と 気づく ことが大切です
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.2確認日 2026年10月24日
面接での 話し方の例
書き始める
「並んでいない
場合は 辞書で O(n) の 時間と O(n) の 記憶でした。 今回は 小さい 順なので、 両端に 指を 置いて、 和が 小さければ 左を 進め、 大きければ 右を 戻します。 時間は O(n) のまま、 記憶は O(1) に できます。」
書き終えたら、
「例 1 の
[1, 3, 4, 8, 11]で目標 15 を たどります。 1 と 11 で 12 は 小さいので、 左を 進めます。 3 と 11 で 14 も まだ 小さいので、 また左を 進めます。 4 と 11 で 15 に なったので、 [2, 4]を返します。」