#LeetCode：1. Two Sum

題目大綱

此題要找出陣列中是否有兩個數字能夠加起來等於指定的數字，並將找到的兩個數字回傳回來。

測試資料

輸入資料

[2,7,11,15]
9

輸出資料

[0,1]

題目網址

LeetCode Online Judge

解法思考

建 Hash 表將所選到之數字 a 所不足的那格 target - a 把自己的 index (i) 紀錄下來，這樣等到該不足之數 target - a 出現的時候可以直接查到與第 i 格湊起來即是答案。

解法程式碼

Kotlin(172ms)

/*******************************************************/
/* LeetCode 1. Two Sum                                 */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2020/05/06                                 */
/*******************************************************/
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val complementMap = mutableMapOf<Int, Int>()

        for (i in nums.indices) {
            if (complementMap.containsKey(nums[i])) {
                val complementNumber = complementMap[nums[i]]
                if (complementNumber != null) {
                    return intArrayOf(complementNumber, i)
                }
            }

            complementMap[target - nums[i]] = i
        }

        return IntArray(0)
    }
}

C++(10ms)

/*******************************************************/
/* LeetCode 1. Two Sum                                 */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/05/23                                 */
/*******************************************************/
class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
    map<int, int> complementMap;
    for(int i = 0 ; i < nums.size() ; ++i){
      auto complement = complementMap.find(nums[i]);
      if(complement != complementMap.end()){
        int result[] = {complement->second, i};
        return vector<int>(result, result + 2);
      }
      complementMap[target - nums[i]] = i;
    }
  }
};