NeetCode 150 [Two Pointers]:medium 1/3

NeetCodeのSolutionを書いていく

Two Sum II Input Array Is Sorted

問題概要

整数の配列numbersと目標とする数値のtargetが与えられます。
numbersは昇順ソートされています。
numbersの中から足し合わせてtargetとなる2つのindexを返しなさい。
index1とindex2は同じは許容されません。
正しい答えは必ずに１つ存在します。

• 制約
  • 入力の配列数は 2 以上 1000 以下
  • 数値は -1000 以上 1000 以下
  • 目標は -1000 以上 1000 以下

計算回数：O(n)
メモリ：O(1)
nはnumsの配列数

例

Input: numbers = [1,2,3,4], target = 3
Output: [1,2]

メモ

使えるメモリが少ない。配列はソート済み。
numbersの数字自体は重複しないと記載がないので、numbers = [2,2], target = 4、みたいな組み合わせはありそう。
indexは2つと決まっているので、numbers = [1,1,1,1], target = 4、という場合はない。
全ての値の組み合わせを確認すればよいが、それだとO(n^2)になってしまう。

昇順になっていることをうまく使う必要がありそう。
target以上の数字は使えないので除外できそうだが、これは設問によって計算が削減できる場合があるだけで回答ではあまり意味はなさそう。
2つの組み合わせで、計算はO(n)許可されているから、「target-１つ目の数字」が存在すればそのindexを返せばよいか。

from typing import List


class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i, number in enumerate(numbers):
            if (target - number) in numbers[i + 1 :]:
                return [i + 1, numbers[i + 1 :].index(target - number) + i + 1 + 1]
        return [0, 0]  # ここにはコない