原题地址：
https://leetcode.com/problems/two-sum/description/
题目：
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
解法：
这是很简单的一道题目，也是LeetCode的第一道题，首先想到的肯定是最基本的暴力方法，用两层循环就解决了。
//解法一
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> temp; int size = nums.size(); for (int i = 0; i < size - 1; i++) { for (int j = i + 1; j < size; j++) { if (nums[i] + nums[j] == target) { temp.push_back(i); temp.push_back(j); break; } } } return temp; } };
这个算法的时间复杂度为O(n^2)，假如不break的话，是会TLE的。
实际上有很多时间复杂度为O(n)的解法，我自己的另一种方法就是：新开一个数组a，把nums里面的值作为新数组a的下标，nums各元素的位置作为新数组a中的值。循环一遍，当a[target - num[i]]不为0时，就说明i和当前的a[target - num[i]]就是所要的结果。有点类似于桶排序的想法；但值得注意的是由于nums里面元素的值有可能为负数，不能作为下标，因此要作一些变化：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> temp; int size = nums.size(); int * a = new int[1000000]; for (int i = 0; i < 1000000; i++) { a[i] = 0; } for (int i = 0; i < size; i++) { a[nums[i] + 500000] = i; } for (int i = 0; i < size; i++) { if (a[target - nums[i] + 500000]) { temp.push_back(i); temp.push_back(a[target - nums[i] + 500000]); break; } } delete [] a; return temp; } };
写起来有点复杂，但是具体的思想就在里面。其实也可以用C++里面的容器来做，更简单（下面的代码来自于：http://www.cnblogs.com/grandyang/p/4130379.html）
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> m; vector<int> res; for (int i = 0; i < nums.size(); ++i) { m[nums[i]] = i; } for (int i = 0; i < nums.size(); ++i) { int t = target - nums[i]; if (m.count(t) && m[t] != i) { res.push_back(i); res.push_back(m[t]); break; } } return res; } };
原文：http://www.cnblogs.com/fengziwei/p/7501933.html