第167回 2つの数の和II - 入力順序配列

問題出典：パワーバックル

問題

昇順に並べ替えられた配列が与えられたとき、その和が目的の数に等しい2つの数を求めなさい。

この関数は、2 つの添え字 index1 と index2 を返す必要があります。

説明

• 返される添え字の値は、0 から始まりません。
• 各入力は一意の答えにのみ対応し、同じ要素を再利用することはできないと仮定できます。

例

 : numbers = [2, 7, 11, 15], target = 9
 : [1,2]
 : 2 と7の和は目標数9に等しい したがってindex1= 1, index2 = 2 。

問題解決のアイデア

アイデア：ダブルポインター

まず問題を見直してみてください、まず問題で与えられている配列は順番に並んでいます、この前提があるので、ダブルポインタを使って範囲を絞り込むという考え方ができます、そして答えを見つけてください。

ここで、まず問題文に書かれている条件を確認してください：

• 返される添え字は 0 からではなく、1 から始まります。
• 質問にはユニークな解答があるので、答えを見つけることは直接返すことができます。

さて、アルゴリズムの具体的なアイデアです：

• leftとrightの2つのポインタを定義します；
• two_sum に設定された 2 つのポインタに対応する数値を合計し、target と比較します：
  • two_sum == target の場合、[left + 1, right + 1] を返します。
  • two_sum > target の場合、右ポインタを前方に移動します；
  • two_sum < target の場合、左ポインタを後方に移動します。

アルゴリズムは以下のように実装されています：

具体的なコードの実装は以下の通り。

コードの実装

class Solution:
 def twoSum(self, numbers: List[int], target: int) -> List[int]:
 length = len(numbers)
 # 配列の先頭と末尾にダブルポインタを定義する。
 left = 0
 right = length - 1
 while left < right:
 # ポインタに対応する数値を合計し、ターゲットと比較する。
 two_sum = numbers[left] + numbers[right]
 # 添え字は 1 から数えるので、等しいときは添え字の値を返す。+1
 if two_sum == target:
 return [left + 1, right + 1]
 # 2つの数値の和が目標より大きい場合、右ポインタを動かして2つの数値の和を小さくする。
 elif two_sum > target:
 right -= 1
 # 2つの数値の和が目標より小さい場合、左ポインタを動かして2つの数値の和を大きくする。
 else:
 left += 1
 return None