Two Sum

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

if문 안에만 return 넣으면 안된다... for문 밖에도 return 넣어줘야 한다.

완전탐색 해야하니 머리 아프게 dp로 풀 필요도 없이 깔쌈하게 2중 for문 돌리면 된다. 

혹은 unordered_map을 사용하면 다음처럼도 된다.

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> ans;
    unordered_map<int, int> hash_table;
    for (int i = 0; i < nums.size(); i++) {
      int key = target - nums[i];
      if (!hash_table.count(key)) {
        // unordered_map search time O(1)
        hash_table[nums[i]] = i;
      } else {
        ans = {hash_table[key], i};
        return ans;
      }
    }
    return ans;
  }
};

처음에 만약 없다면 key를 nums의 값으로 하고 index를 value로 하여 저장한다. int key 부분을 보면 알겠지만 nums의 값들이 필요한 것이지 idx는 나중에 필요하다. nums의 값이 우선.