入力された整数の配列の中、和が特定の目標に等しい2数のインデックスを求めよ。
一つの入力に対して唯一の正解が存在することを仮定してもいい。
例：
nums = [2, 7, 11, 15], target = 9,
nums[0] + nums[1] = 2 + 7 = 9 ので、 [0, 1] をリターンする.
解：
さすが第一問はやさしいものです。解決はいくつでもある。ブルート・フォースだとO(n^2)になりますが、先に入力配列をソートするとO(nlogn)で済む。
O(n)の時間計算量を目指して、O(n)の空間を使ってハッシュテーブルでやってみた。
C#のコードは以下です。
public class Solution
{
public int[] TwoSum(int[] nums, int target)
{
Dictionary<int,int> buffer = new Dictionary<int,int>(nums.Length*2);
for(int i=0; i<nums.Length; ++i)
{
int item = nums[i];
if (buffer.ContainsKey(target-item))
{
return new int[]{buffer[target-item], i};
}
buffer[item] = i;
}
return null;
}
}