LeetCode 1. Two Sum

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].

解析：
给定一个数组和一个值，求出这个数组中两个值的和等于这个给定值的坐标。
输出的结果要求：1坐标较小的放在前面，较大的放在后面。2每一组输入只有一个结果。3输出结果不能使用同一个元素
最简单直接的方法，采用两层循环，两两比较，时间复杂度为\(O（n^2）\)，这样会超时。
解法1：
通过牺牲空间复杂度来优化时间复杂度，采用哈希表hash_map, 查找的时间复杂度理想情况下是O(1)。先把输入数组的所有元素存到hashmap中，一次循环就行， 时间复杂度为O(n)。
具体代码如下：
[cc lang=”C++”]
class Solution {
public:
vector twoSum(vector& nums, int target) {
vector result;
if(nums.size() <= 1) return result; unordered_map tempMap;//hash_map key元素,value下标
for(int i = 0; i < nums.size(); ++i) tempMap[nums[i]] = i; for(int i = 0; i < nums.size(); ++i) { int another = target - nums[i]; if(tempMap.find(another)!=tempMap.end()) { int index = tempMap[another]; if(index == i)//元素不能相同 continue; if(index < i) { result.push_back(index); result.push_back(i); return result; } else { result.push_back(i); result.push_back(index); return result; } } } } }; [/cc] 解法2： 先对数组进行排序，然后通过夹逼的方法来查找元素。但有一点需要注意，排序之后元素的顺序发生了变化，下标也发生了变动。可以定义结构体，存放数组中的元素和原始的下标。 具体代码如下： [cc lang="C++"] typedef struct node{//定义结构体，存放数组元素和对应的下标 int index; int var; node(){}; node(int i, int v):index(i),var(v){} }Node; bool compare(const Node &a, const Node &b)//自定义的比较函数 { return a.var < b.var; } class Solution { public: vector twoSum(vector& nums, int target) {
size_t vect_len = nums.size();
vector index_vect;
vector nodes_vect(vect_len);
for(int i =0; i < vect_len; ++i)//对输入原始依次构建结构体 { nodes_vect[i] = Node(i, nums[i]); } sort(nodes_vect.begin(), nodes_vect.end(), compare);//根据元素大小进行排序 int l=0,r=vect_len-1; while(l < r)//二分查找 { int sum = nodes_vect[l].var + nodes_vect[r].var; if(sum == target) { int min_index = min(nodes_vect[l].index, nodes_vect[r].index); int max_index = max(nodes_vect[l].index, nodes_vect[r].index); index_vect.push_back(min_index);//小的下标在前 index_vect.push_back(max_index); break; }else if(sum < target) { ++ l; }else { -- r; } } return index_vect; } }; [/cc] 参考： http://blog.csdn.net/linhuanmars/article/details/19711387 https://siddontang.gitbooks.io/leetcode-solution/content/array/sum.html