1. Two Sum

发表于 | 分类于 | 阅读次数
字数统计 699 | 阅读时长 4

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.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return[0, 1].

UPDATE(2016 / 2 / 13) :The return format had been changed to zero - based indices.Please read the above updated description carefully.

思路：

　　首先，不能对该数组作任何预处理。因为要求返回是原始数组的下标，如果对数组进行了排序，那么下标就会乱。（如果是有序数组，可以用双指针来做，参见Two Sum II - Input array is sorted）
　　很容易想到用<value, index>的映射表。遍历numbers，在映射表中寻找target-numbers[i]，若找到则结束，返回存储的下标+1和当前下标+1. （注意题目中规定，以1作为起始下标），若找不到则将<numbers[i], i>加入映射表。

NOTE:

　　这里又有一个问题，C++中常用的映射表有map, unordered_map。

1
2
3
4
5
6
7
map:
　　Internally, the elements in a map are always sorted by its key following a specific strict weak ordering criterion indicated by its
internal comparison object (of type Compare).
　　map containers are generally slower than unordered_map containers to access individual elements by their key, but they allow the direct iteration
on subsets based on their order.

map::operator[]:Logarithmic in size.（根据键值取元素时间复杂度是对数级别）
1
2
3
4
5
6
7
8
9
unordered_map:
　　Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values,
but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values (with a constant average time complexity on average).
　　unordered_map containers are faster than map containers to access individual elements by their key, although they are generally less efficient
for range iteration through a subset of their elements.

unordered_map::operator[]:
　　　　　　　　　Average case: constant.（根据键值取元素平均时间复杂度是常数级别）
　　　　　　　　　Worst case: linear in container size.（根据键值取元素最坏时间复杂度是线性级别）

本题只需要根据key访问单个元素，因此unordered_map更合适。
时间复杂度O(n)：一次遍历
空间复杂度O(n)：unordered_map
ps: 严格来说，target-numbers[i]可能溢出int，因此提升为long long int更鲁棒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> res;
		unordered_map<int, int> hash;
		for (int i = 0; i < nums.size(); i++)
		{
			if (hash.find(target-nums[i])==hash.end())
			{
				hash[nums[i]] = i;
			}
			else {
				res.push_back(hash[target - nums[i]]);
				res.push_back(i);
				return res;
			}
		}

	}
};

int main()
{
	vector<int> nums = { 2, 7, 11,7,15,7 };
	int target = 14;

	Solution s;
	auto re = s.twoSum(nums, target);

	system("pause");
	return 0;
}

　Java Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++) {
            int sub = target - nums[i];
            if(map.containsKey(sub))
                return new int[] {i,map.get(sub)};
            else
                map.put(nums[i],i);
        }

        return null;
    }
}