Two sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
C++ Solution
思路:使用O(n2)遍历,先确定第一个数，然后再剩余的数中找是否有第二个数与之相加等于target值。最后返回下标集合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// C++
// O(n2) Solution
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i, j;
for (i = 0; i < nums.size(); i++) {
for (j = i + 1; j < nums.size();j++) {
if (nums[i] + nums[j] == target) {
return vector<int>{i,j};
}
}
}
return vector<int>{};
}
};
Go Solution
思路: 使用O(n1),需要使用到集合,考虑到输入可能有重复的键值，实现一套一键多值的实现。首先将所有值存入Multimap中，遍历所有键值对。 当key值有多值时，且相加为target值时，直接返回对应的下标数组。当key值只有单值时，查找对应的target-key在集合中是否存在，如果存在， 则返回两者的下标。但注意的是需要排除重复使用了单值的情况，即刚好遍历的值为target值的一半时，且数量只有一个时，计算target-key时，会再从集合中 获取到该值，造成误判断。
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
33
34
35
36
37
38
39
40
41
42
// go
// O(n1) Solution
type Multimap map[int][]int
type keyValues struct {
key int
values []int
}
func (multimap Multimap) Add(key, value int) {
if len(multimap[key]) == 0 {
multimap[key] = []int{value}
} else {
multimap[key] = append(multimap[key], value)
}
}
func (multimap Multimap) Get(key int) []int {
if multimap == nil {
return nil
}
values := multimap[key]
return values
}
func twoSum(nums []int, target int) []int {
var myMap Multimap
myMap = make(Multimap);
for index, num := range nums {
myMap.Add(num, index)
}
for key, vals := range myMap {
if len(vals) > 1 && key * 2 == target {
return vals
}
if _, ok := myMap[target - key]; ok {
if target - key != key {
return append(myMap[key], myMap[target - key][0])
}
}
}
return nil
}
