Difficulty: Easy

暴力解法肯定不行。

注意到两点：

1. 最后要返回在原始数组中的位置
2. 数字可以有重复，所以不可以简单用 map 或 set 全装进去

Solution 1:

先排序，然后转化为双指针，找到两个数字之后，再在原来的数组中找到它们的位置。复杂度O(nlogn)。

class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    auto nums0 = nums;
    sort(nums.begin(), nums.end());
    int i = 0, j = nums.size() - 1;
    while (i < j) {
      int sum = nums[i] + nums[j];
      if (sum < target)
        i++;
      else if (sum > target)
        j--;
      else
        break;
    }
    for (int k = 0; k < nums0.size(); k++)
      if (nums0[k] == nums[i]) {
        i = k;
        break;
      }
    for (int k = nums0.size() - 1; k >= 0; k--)
      if (nums0[k] == nums[j]) {
        j = k;
        break;
      }
    return {i, j};
  }
};

* Solution 2:

渐进地将数字装入map中，可以避免重复数字的出现。同时使用map记录数字在原数组中的位置。

class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> m;
    for (int i = 0; i < nums.size(); i++) {
      if (m.count(target - nums[i]) == 0) {
        m.insert({nums[i], i});
      } else {
        return {i, m[target - nums[i]]};
      }
    }
    return {0, 0};
  }
};