首页 > ACM题库 > LeetCode > leetcode-Two Sum[题解]
2014
03-19

leetcode-Two Sum[题解]

题目Two Sum  面试频率:5  难度:2   (1-5)

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

题目大意:给一个数组,找出其中是否有两个数之和等于给定的值。类似的还有3 sum ,4 sum ..等 K sum 问题。其实原理是差不多的,这样想:先取出一个数,那么我只要在剩下的数字里面找到两个数字使得他们的和等于(target – 那个取出的数)。

解法1:先排序,然后从开头和结尾同时向中间查找,原理也比较简单。复杂度O(nlogn)

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--;
        }
    }
};

解法2:使用HashMap。把每个数都存入map中,任何再逐个遍历,查找是否有 target – nubmers[i]。 时间复杂度 O(n)

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));因为第二种解法如果数组有重复元素 就不正确

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