Code2 两数之和

题目

（leetcode1）
给定一个整数数列，找出其中和为特定值的那两个数。
你可以假设每个输入都只会有一种答案，同样的元素不能被重用。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

代码

// C++
#include <iostream>
#include <unordered_map>

using namespace std;
class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> result;
    std::unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); ++i) {
      auto it = map.find(target - nums[i]);
      if (it != map.end()) {
        result.push_back(it->second);
        result.push_back(i);
        break;
      } else {
        map[nums[i]] = i;
      }
    }
    return result;
  }
};

测试

int main() {
  vector<int> nums = {1, 2, 3, 3, 5};
  int target = 6;

  do {
    std::cout << "nums: ";
    for (auto i : nums) {
      std::cout << i << " ";
    }
    std::cout << ", target:" << target << std::endl;
  } while (false);

  Solution s;
  auto result = s.twoSum(nums, target);
  if (!result.empty()) {
    std::cout << "result: ";
    for (auto i : result) {
      std::cout << i << " ";
    }
  } else {
    std::cout << "not found." << std::endl;
  }

  std::cin.get();
  return 0;
}

结果：

nums: 1 2 3 3 5 , target:6
result: 2 3