LeetCode－1. Two Sum

難度:Easy

描述:給定一個整數陣列 nums 和一個整數 target，返回兩個數字的索引，使它們加起來等於 target。 

你可以假設每個輸入都會有確切一個解決方案，而且你不能使用同一個元素兩次。 

你可以以任何順序返回答案。

方法一 窮舉法（Exhaustive）：

思路：

1.逐一兩兩相加比對，是否達到目標數值。

2.將合法組合回傳即可。

Time Complexity : O(n2)

Runtime : 390 ms        (18.85%)

Memory : 10.21 MB     (61.84%)

 

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        int n = nums.size();
        for(int i = 0;i<n && ans.empty();i++){
          for(int j = i+1;j<n && ans.empty();j++ ){
            if(nums[i] + nums[j] == target){
              ans.push_back(i);
              ans.push_back(j);
            }
          }
        }
        return ans;
    }
};

方法二 (Map)：

思路：

1.於MapTable中找尋是否存在(target - 當前數字)。

2.若存在，表示當前數字與(target - 當前數字)相加即為target，本題得解。

3.若不存在，將當前數字存入MapTable。

Time Complexity : O(n)

Runtime : 8 ms            (81.03%)

Memory : 11.22 MB     (13.84%)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        map<int,int> mappingNum;
        int n = nums.size();
        for(int i = 0;i<n && ans.empty();i++){
          int val = target - nums[i];
          auto p = mappingNum.find(val);
          if( p !=mappingNum.end()){
            ans.push_back(i);
            ans.push_back(p->second);
          }else{
            mappingNum[nums[i]] = i;
          }
        }
        return ans;
    }
};