問題概要
1. Two Sum
整数の配列numsと整数targetが与えられたとき、それらの和がtargetになるような2つの数値のインデックスを返す関数を作成する。
各入力には正確に1つの解が存在すると仮定し、同じ要素を2回使用することはできない。
答えはどのような順序で返しても良い。
入力例
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
制約
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
実装例
for文で回す事も出来るがワンパス・ハッシュ・テーブルアルゴリズムが使える。
具体的には反復してハッシュテーブルに要素を挿入している間に、現在の歩数が既にハッシュテーブルに存在するかをチェックしてもし存在すれば、インデックスに返す事が出来る。
const twoSum = function(nums, target) {
const comp = {};
for(let i=0; i<nums.length; i++){
if(comp[nums[i] ]>=0){
return [ comp[nums[i] ] , i]
}
comp[target-nums[i]] = i
}
};
