2014
03-19

# leetcode-Two Sum[题解]

http://oj.leetcode.com/problems/two-sum/

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

typedef struct Node{
int id,val;
}Node;
bool compare(const Node & a,const Node & b){
return a.val < b.val;
}

class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
Node nodes[numbers.size()];
for(unsigned int i=0; i<numbers.size(); i++){
nodes[i].id = i+1;
nodes[i].val = numbers[i];
}
sort(nodes, nodes+numbers.size(), compare);
int start=0,end=numbers.size()-1;
vector<int> ans;
while(start < end){
if(nodes[start].val + nodes[end].val == target){
if(nodes[start].id > nodes[end].id)
swap(nodes[start].id , nodes[end].id);
ans.push_back(nodes[start].id);
ans.push_back(nodes[end].id);
return ans;
}else if( nodes[start].val + nodes[end].val < target ){
start++;
}else
end--;
}
}
};

vector<int> twoSum(vector<int> &numbers, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> res;
int length = numbers.size();
map<int,int> mp;
for(int i = 0; i < length; ++i)
mp[numbers[i]] = i;
map<int,int>::iterator it = mp.end();
for(int i = 0; i < length; ++i)
{
it = mp.find(target - numbers[i]);
if(it != mp.end())
{
res.push_back(min(i+1,it->second +1));
res.push_back(max(i+1,it->second +1));
break;
}
}
return res;
}

	vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> res;
int length = numbers.size();
map<int,int> mp;
int find;
for(int i = 0; i < length; ++i){
find=mp[target - numbers[i]];
if( find ){
res.push_back(find);
res.push_back(i+1);
break;
}
mp[numbers[i]] = i+1;
}
return res;
}

1. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确

• 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法