# 1-Two Sum
###### tags: `Easy`


1. 暴力解
2. hash table
3. two pointer，但因為輸入沒有排序過，要再排序才能用two pointer，且因為要回傳的是位置而非數值，又要再找數值在原本陣列的對應位置，所以比hash table省一點空間，但速度沒比較快

## Solution
### Brute force solution
- 最簡單的寫法:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for n in range(len(nums)):
            rest = target - nums[n] 
            for m in range(len(nums)):
                if nums[m] == rest and m != n:
                    idx = n
                    idx2 = m
                    return idx, idx2


- 大神寫法

class Solution(object):
    def twoSum(self, nums, target):
        store_val={}
        for i,num in enumerate(nums):
            store_val[num]=i 
        for i,num in enumerate(nums):
            search_val = target - num 
            if search_val in store_val:
                if i!=store_val[search_val]:
                    return [i,store_val[search_val]]


## Hash table solution
C++ version (return value):

#include <vector>
using namespace std;

vector<int> twoNumberSum(vector<int> array, int targetSum) {
  // Write your code here.
  unordered_set<int> nums;
  for (int num: array){
      int potentialMatch = targetSum - num;
      if (nums.find(potentialMatch) != nums.end()){
          return vector<int>{potentialMatch, num};
      }else{
          nums.insert(num);
      }
  }
  return {};
}

C++ version (return idex):

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        
        for(int i = 0; i < nums.size(); i++) {
            if(mp.find(target - nums[i]) != mp.end()) {
                return {i, mp[target- nums[i]]};
            }
            
            mp[nums[i]] = i;
        }
        
        return {};
    }
};

### Two pointer solution

        vector cp = nums;  
		int start = 0, end = nums.size()-1, sum;  
        sort(cp.begin(),cp.end());  
        while(start < end){
            sum = cp[end] + cp[start];
            if(sum == target){
                int x = -1, y = -1;
                for(int i = 0; i < nums.size(); i++){
                    if(x != -1 && (nums[i] == cp[end]  || nums[i] == cp[start])){
                        y = i;
                    }else if(x == -1 &&(nums[i] == cp[start] || nums[i] == cp[end])){
                        x = i;
                    }
                    if(y > 0)
                        return {x,y};
                }
            }
            else if(sum < target){
                start++;
            }else{
                end--;
            }
        }
        return {-1,1};