こちらは「Two Sum」のPythonによる解答例となっております。この問題は、整数の配列と目標の数値が与えられたときに、配列内の2つの数値の合計が目標に等しくなるように、2つの数値のインデックスを返す問題です。
問題
整数の配列「nums」と目標値「target」が与えられたとき、配列内の2つの数値の合計が目標に等しくなるように、2つの数値のインデックスを返します。
numsには、2つ以上の要素が含まれます。10^9 <= nums[i] <= 10^92 <= nums.length <= 10^410^9 <= target <= 10^9答えは一意に定まります。
解法
この問題は、ハッシュマップを用いた1つのアプローチがあります。ハッシュマップは、配列内の要素を快速に検索できるため、この問題に適しています。
アルゴリズムの概要を以下に述べます。
- ハッシュマップを初期化します。
- 配列を1つずつ反復処理します。
- 要素をハッシュマップに追加します。
target - nums[i]の値を計算し、ハッシュマップ内に存在するかどうかを確認します。- 存在する場合、現在のインデックスとハッシュマップ内のインデックスを返します。
- 存在しない場合、次の要素に移動します。
Pythonコード
以下のコードが、「Two Sum」を解くためのPythonプログラムとなります。
### Function ##################################################################
def solve(num=0):
solver = Solution().twoSum
if 1 <= num <= Input().input: id_LIST = [num]
else: id_LIST = [id+1 for id in range(Input().input)]
for id in id_LIST:
data = Input(id)
ans = solver(data.nums, data.target)
result = "OK" if ans==data.ans else "NG"
print(f"[{str(id).zfill(3)}] {result}")
### Class #####################################################################
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
2 <= nums.length <= 10**4
-10**9 <= nums[i] <= 10**9
:type target: int
-10**9 <= target <= 10**9
:rtype: List[int]
"""
h = {}
for i, num in enumerate(nums):
n = target - num
if n not in h:
h[num] = i
else:
return [h[n], i]
#==============================================================================
class Input:
def __init__(self, num=0):
if num == 1:
self.nums = [2,7,11,15]
self.target = 9
self.ans = [0,1]
elif num == 2:
self.nums = [3,2,4]
self.target = 6
self.ans = [1,2]
elif num == 3:
self.nums = [3,3]
self.target = 6
self.ans = [0,1]
else:
self.input = 3
### Main ######################################################################
if __name__ == "__main__":
solve()
###############################################################################