LeetCode | Two Sum

1題目

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

2解答

2.1 兩兩相加

這個應該是所有人都想得到的，我先嘗試了這個方法，結果提示逾時，看來必須用複雜度低的算法了。

2.2  排序後再相加

這個也是第一直覺就應該想到的，通過排序可以省掉很多無用的計算，有個問題是必須再查找回原來的數組下标，開始也漏了這個點。

2.3 hash_map查找法

這個是提示采用的方法，不過如果用c語言還得去實作這個map。是以就沒有再嘗試了，思路比較取巧。