Two Sum 題目連結
官網題目說明：
解法：
從給定的一組值內找出第一組兩數相加剛好等於給定的目標值，暴力解很簡單(只會這樣= =)，兩個迴圈，只要找到相加的值就跳出。
/// <summary>
/// 暴力解O(n2)
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <returns></returns>
public static int[] TwoSum(int[] nums, int target)
{
int[] result = new int[];
for (int i = ; i < nums.Length; i++)
{
for (int j = i + ; j < nums.Length; j++)
{
if (nums[i] + nums[j] == target)
{
result[] = i;
result[] = j;
break;
}
}
} return result;
}
另題目內有討論時間複雜度表現較為優秀的解法，也一併實作看看。
此為兩步驟(two pass)hashtable，先將給定值放入hashtable(此用dictionary，圴為key/value的組合)，但有可能會找到自已
/// <summary>
/// two pass hashtable 解, O(1)，如果有碰撞(collision)則為O(n)
/// 因為先把所有數放進hashtable，有可能找到自已
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <returns></returns>
public static int[] TwoSum2(int[] nums, int target)
{
Dictionary<int, int> map = new Dictionary<int, int>(); for (int i = ; i < nums.Length; i++)
{
map[nums[i]] = i;
} for (int i = ; i < nums.Length; i++)
{
//餘數
int complement = target - nums[i]; if (map.ContainsKey(complement) && map[complement] != i)
{
//當前數的index & 餘數的index
return new int[] { i, map[complement] };
}
} throw new ArgumentNullException();
}
此為one pass hashtable，最大特點在先找再放值，考慮迴圈的情形下
i == 0，hashtable內無值
i == 1，找的是hash[0]
i == 2，找的是 hash[0] hash[1]
i == n，找的是hash[0]..hash[n - 1]
不會有碰撞的情形
/// <summary>
/// one pass hashtable
/// hashtable內永遠只有 nums[i-1],nums[i-2]...的數，不會找到自已
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <returns></returns>
public static int[] TwoSum3(int[] nums, int target)
{
Dictionary<int, int> map = new Dictionary<int, int>(); for (int i = ; i < nums.Length; i++)
{
int complement = target - nums[i];
if (map.ContainsKey(complement))
{
return new int[] { map[complement], i };
} map[nums[i]] = i;
} throw new ArgumentException();
}
個人的練習與紀錄，歡迎大家討論與指教