LeetCode #1 – 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

第一次做leetcode,感觉上面的题比较高大上,而且是很多找工作的面试笔试题,一共200来道题,不会有做不完的感觉,题目质量挺高的。

这道题题意比较简单,就是找两个下标不同的数,使他的和为target。如果用两层循环暴力搜索的话,会超时。用map保存下标,然后每次查询两个数的差值,查询的复杂度为o(log n),因此总的时间复杂度为o(n log n)。

下面是C++和Python实现。

 

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> res;
		map<int, int> pos;
		for (size_t i = 0; i != nums.size(); ++i)
			pos[nums[i]] = i;
		for (size_t i = 0; i != nums.size(); ++i) {
			int fuck = target - nums[i];
			if (pos.count(fuck) && pos[fuck] > i) {
				res.push_back(i + 1);
				res.push_back(pos[fuck] + 1);
				return res;
			}
		}
	}
};
class Solution:
    def twoSum(self, nums, target):
        pos = {}
        for i in range(len(nums)):
            f = target - nums[i]
            if f in pos:
                return [pos[f] + 1, i + 1]
            pos[nums[i]] = i

欢迎留言