167.Two-sum-Ⅱ input-array-is-sorted 解答例・ポイント

問題内容

与えられたリスト内の数字について、和が目標の数になるような2つの数字の組み合わせをリストにして返しなさいというもの。

解答例

sample

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1

        while left < right:
            total = numbers[left] + numbers[right]

            if total == target:
                return [left + 1, right +1]
            elif total > target:
                right -= 1
            else:
                left += 1

この問題の難しいところ

「リスト内の数字をいろいろと組み合わせて作ることができる数字を羅列してから目標の数字と比べる」という考え方をすると処理時間がデータ量次第で膨大になったり、エラーが発生しやすくなったりする。

ポイント

解答例では、「まずリスト左右の端にポインタを置き、ポインタが指す数字の和と目標値の大小を見て調整する」という考え方のもとプログラムされている。和が目標値よりも大きければ左のポインタをずらすことで和を小さくできる。逆も同様。このような調整は入力されるリストがソート済みであるため可能になっている。