# 15-3Sum

###### tags: `Medium`

## Question:
https://leetcode.com/problems/3sum/

## Key:
*解需要排序

想法一：結合TwoSum，但先sort，因sort過了，接下來只要從剩下的找，另外確保找到的值較大或不相等即可。

## Solution

vector<vector<int>> threeNumberSum(vector<int> array, int targetSum) {
  vector<vector<int>> answer;
  sort(array.begin(), array.end());
  unordered_map<int, int> hashedArray;
	
  for (int i = 0; i < array.size(); i++){
      hashedArray[array[i]] = i;
  }
  for (int i = 0; i < array.size(); i++){
      int remainSum = targetSum - array[i];
      for (int j = i+1; j < array.size(); j++){
          int potentialMatch = remainSum - array[j];
          auto it = hashedArray.find(potentialMatch);
          if (it != hashedArray.end() && it->first > array[j] && it->first != array[j]){
              answer.push_back(vector<int>{array[i], array[j], potentialMatch});
          }
      }
  }
  return answer;
}

較優想法：sort完後從第一個開始，對其後方的剩餘數列排列組合找符合的，從左右邊夾著往中間搜索。
*少用了unordered_map

## Two pointer solution
先把輸入的 array sort 完，然後依序把每個 element 當作 nums[i]，剩下就是尋找 nums[j]+nums[k] == -nums[i]