LeetCode解説　一日一問　1.towsum

LeetCodeって？
問題
回答
1. コード
結果

LeetCodeって？

Just a moment...

LeetCodeとは、アルゴリズムやデータ構造を実践を通して学べる海外のプログラミング学習サイトです。

2022年12月現在2,000問を超える問題が登録されています。

各問題では、特定の入力をしたときに特定の返り値を出力する関数を作成することを求められます。

正誤判定は自動で行われます。

使用できる言語は、C++、C#、JAVA、Python3、Go、JSなど19言語が用意されています。

私はPython3で解いています。

問題

Just a moment...

タイトル：1. Two Sum

難易度：easy

内容：

複数の整数の入ったnums(List[int])の中から、足すとtarget(int)と同じ値になるように２つの数値を抽出し、そのインデックスを返す。答えとなる組み合わせは必ず１つだけ存在する。

例：

nums =

[8,0,-2,4,-4,2,6,3]
target = 9
output= [6,7]

numsの中で足すと9になる組み合わせは6+3のみ。なので期待する帰り値は6と3のインデックスの[6,7]となります。

なおnumsの中にはtargetより大きい数値も含まれていますが、numsの値はマイナスも取りうるので和をとるとtargetになることがあり得ます。

回答

何はともあれソートしたほうが良さそうなのでソートします。

この時、返り値は元のリストのインデックスに基づかなければならないので、ソートされたリストではなく、ソートされたリストのインデックスを保存します。

sorted_index = np.argsort(nums)

次に、ソート済みnumsの左端の値（最小値）と右端の値（最大値）を初期値とします。

ついでに足し算の答えを初期化します。

l_index = 0
r_index = len(nums) - 1
ans = None

-4 + 8 = 4 < 9

なのでtargetより小さく、最も大きい値8と組み合わせても、-4で9は作れません。

なので-4は候補から消え、左端を次の値に移動します。

-2、0でも9は作れないので同様に候補から消えます。

同様にしていくと2+8=10となり今度は9を超えてしまいました。

現在最小の2と９が作れないので８も消えます。同様に進めていくと、答えの3+6にたどり着きます。

コード

# 全文
import numpy as np
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sorted_index = np.argsort(nums)

        l_index = 0
        r_index = len(nums) - 1
        ans = None
        while ans != target:
            ans = nums[sorted_index[l_index]] + nums[sorted_index[r_index]]
            if ans > target:
                r_index -= 1
            elif ans < target:
                l_index += 1
        return [sorted_index[l_index],sorted_index[r_index]]

計算量はO(N)です。