Monthly Archives: October 2015

LeetCode Two Sum

LeetCode 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,从#1开始!
这一题要从一个序列中找出两数之和为target的两个数。因为序列无序,所以能够想到的最简单的方法就是先对数组排序,然后设置头尾两个指针,判断求和情况和target的大小关系。当得到两个数之后,再在原序列中找这两个数的index,注意index1<index2。
完整代码如下:

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> nums_copy = nums;
		sort(nums_copy.begin(), nums_copy.end());
		int i = 0, j = nums_copy.size() - 1;
		while (i != j)
		{
			if (nums_copy[i] + nums_copy[j] == target)
				break;
			else if (nums_copy[i] + nums_copy[j] < target)
				i++;
			else
				j--;
		}
		vector<int> ans(2);
		for (int k = 0; k < nums.size(); k++)
		{
			if (ans[0] == 0 && nums[k] == nums_copy[i])
				ans[0] = k + 1;
			else if (ans[1] == 0 && nums[k] == nums_copy[j])
				ans[1] = k + 1;
		}
		if (ans[0] > ans[1])
			swap(ans[0], ans[1]);
		return ans;
	}
};

本代码提交AC,用时16MS。
还可以借助hash方法实现O(n)的算法。思路是将nums全部hash存储,然后扫描数组,判断target-nums[i]是否在hash表中。整个运行时间在O(n)。
代码如下:

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		//map<int, int> nums_index;
		unordered_map<int, int> nums_index; // unordered_map比map快
		vector<int> ans(2);
		for (int i = 0; i < nums.size(); i++)
		{
			int added = target - nums[i];
			if (nums_index.find(added) != nums_index.end())
			{
				ans[0] = nums_index[added];
				ans[1] = i + 1;
				return ans;
			}
			nums_index[nums[i]] = i + 1;
		}
	}
};

本代码提交AC,用时还是16MS。
此题测试数据只有16组,真是太少了,如果数据多的话,相信第二种方法会快很多。