001. Two Sum

  • 31.0%

https://leetcode.com/problems/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.

1
2
3
4
5
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.


思路

方法一:

dic, 全部都放入dic, 依次遍历,查找当前值target缺的那部分,要缺的index大于当前的index。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 面试奇虎360时曾遇到过
// beats 45.40% of cppsubmissions.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mapping;
vector<int> result;
for(int i = 0; i < nums.size(); i++){
mapping[nums[i]] = i;
}
for(int i = 0; i < nums.size(); i++){
const int gap = target - nums[i];
if(mapping.find(gap) != mapping.end() && mapping[gap] > i){
result.push_back(i);
result.push_back(mapping[gap]);
}
}
return result;
}
};

方法二:

一遍遍历,一边放入dic

代码实现一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
unordered_map<int, int> map;
for(int i=0; i<nums.size(); i++){
int nex = target - nums[i];
if(map.find(nex)!=map.end()){
res.push_back(i);
res.push_back(map[nex]);
break;
}else{
map[nums[i]] = i;
}
}
return res;
}
};

代码实现二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res(2, -1);
unordered_map<int, int> map;
for(int i=0; i<nums.size(); i++){
int gap = target - nums[i];
if(map.count(gap)){
res[0] = map[gap];
res[1] = i;
return res;
}else
map[nums[i]] = i;
}
}
};

48ms, 59.36%, Apr.23rd, 2016

找出数组中的两个数,这两个数和为target

扫到x时看前面Hash的数里有没有target-x,然后将x也放进Hash表。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dict = {}
for i in range(len(nums)):
if dict.get(target - nums[i], None) == None:
dict[nums[i]] = i
else:
return (dict[target - nums[i]], i)

my code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
maps = {}
for i, num in enumerate(nums):
if target-num in maps:
return [i, maps[target-num]]
maps[num] = i

下面这个方法速度特慢,原因:对每个元素都进行了哈希,总之,无论建立还是查找都费了时间。

上面一种方法,注意,python字典有get方法

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dict = {n: i for i, n in enumerate(nums)}
for i, n in enumerate(nums):
if target-n in dict.keys() and dict[target-n] != i:
return [i, dict[target-n]]

java


https://leetcode.com/articles/two-sum/

Approach #2 (Two-pass Hash Table) [Accepted]

To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

We reduce the look up time from O(n)O(n) to O(1)O(1) by trading space for speed. A hash table is built exactly for this purpose, it supports fast look up in near constant time. I say “near” because if a collision occurred, a look up could degenerate to O(n)O(n) time. But look up in hash table should be amortized O(1)O(1) time as long as the hash function was chosen carefully.

A simple implementation uses two iterations. In the first iteration, we add each element’s value and its index to the table. Then, in the second iteration we check if each element’s complement (target - nums[i]target−nums[i]) exists in the table. Beware that the complement must not be nums[i]nums[i] itself!

1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
throw new IllegalArgumentException("No two sum solution");
}

Complexity Analysis:

Time complexity : O(n)O(n). We traverse the list containing nn elements exactly twice. Since the hash table reduces the look up time to O(1)O(1), the time complexity is O(n)O(n).

Space complexity : O(n)O(n). The extra space required depends on the number of items stored in the hash table, which stores exactly nn elements.

Approach #3 (One-pass Hash Table) [Accepted]

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.

1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}

Complexity Analysis:

Time complexity : O(n)O(n). We traverse the list containing nn elements only once. Each look up in the table costs only O(1)O(1) time.

Space complexity : O(n)O(n). The extra space required depends on the number of items stored in the hash table, which stores at most nn elements.

谢谢你,可爱的朋友。
显示 Gitment 评论