【LeetCode】167. Two Sum II - Input Array Is Sorted 解いてみた【Medium】

問題の概要

昇順にソートされた番号のリストから足したらターゲットになる2つの数字のインデックスを返す

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

最初に考えた解き方

・まあまずインデックス0固定で2つ目の数字を足してターゲットより高くなるまで＝＝をチェック
＞いけるだろう。だが単調である
＞O(（n-1)!)だよねたぶん
問題文にこう書いてあった
The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.
同じ要素使いまくってるな！考え直そう
・一回しか使えないので
＞各要素チェックする際に
＞target - num
＞if それ in nums:
＞for i in range(いまのインデックス+1, len(nums)-1):
＞if それ == nums[i]
＞return いまのインデックス, i
いけそう

for i, num in enumerate(numbers):
    remainder = target - num
    if remainder in numbers:
        for j in range(i + 1, len(numbers)):
            if numbers[j] == remainder:
                return (i+1, j+1)

Time Limit Exceeded
two pointerという題材はどこへ？
考え直そう
思いつかない

何がよくなかったか？

ブルートフォースを考えた時に数字を実際に書いて見てみれば解決策を思いついたのかもしれない

解き方

2ポインター数が大きいなら右を左へ。逆も

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

        while l < r:
            curSum = numbers[l] + numbers[r]

            if curSum > target:
                r -= 1
            elif curSum < target:
                l += 1
            else:
                return [l + 1, r + 1]
        return []

簡単じゃないか

例をを実際に書いてみること
流れを書いてみること
それをしよう

参考資料

おわりに

コードは考えをアウトプットしているにすぎない。
考えがなしにコードは生まれない
ホワイトボード欲しい