LeetCode - 两数之和

题目

给定一个整数数组 nums和一个整数目标值 target,请你在该数组中找出 和为目标值 的那两个整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例1:

1
2
3
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例2:

1
2
输入:nums = [3,2,4], target = 6
输出:[1,2]

示例3:

1
2
输入:nums = [3,3], target = 6
输出:[0,1]

提示:

  • 2 <= nums.length <= 103
  • 109 <= nums[i] <= 109
  • 109 <= target <= 109
  • 只会存在一个有效答案

解题

方法

1. 暴力枚举

遍历数组中的每一个元素,并检查它后面的元素中有没有元素和它之和为指定数值,该方法时间复杂度为 $O(n^2)$,不推荐,代码示例:

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
for i, num := range nums {
for j := i + 1; j < len(nums); j++ {
if num+nums[j] == target {
return []int{i, j}
}
}
}
return nil
}

2. 哈希表【推荐】

方法1复杂度高的原因在于寻找差值的时间复杂度为$O(n)$,可以使用哈希表来存储每个元素及其下标,然后遍历数组中元素,计算差值,从哈希表中判断差值是否存在以及获取下标,该操作时间复杂度为 $O(1)$,总时间复杂度为$O(n^2)$,代码示例:

1
2
3
4
5
6
7
8
9
10
11
func twoSum(nums []int, target int) []int {
var m = make(map[int]int)
for i, num := range nums {
v := target - num
if j, ok := m[v]; ok {
return []int{j, i}
}
m[num] = i
}
return nil
}

单元测试

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
43
44
45
46
47
48
49
// 测试两数之和
func TestTwoSum(t *testing.T) {
type args struct {
nums []int
target int
}
tests := []struct {
name string
args args
want []int
}{
{
name: "01",
args: args{
nums: []int{2, 7, 11, 15},
target: 9,
},
want: []int{0, 1},
},
{
name: "02",
args: args{
nums: []int{3, 2, 4},
target: 6,
},
want: []int{1, 2},
},
{
name: "03",
args: args{
nums: []int{3, 3},
target: 6,
},
want: []int{0, 1},
},
}
for _, tt := range tests {
t.Run(
tt.name, func(t *testing.T) {
if got := twoSum(tt.args.nums, tt.args.target); !reflect.DeepEqual(got, tt.want) {
t.Errorf("twoSum() = %v, want %v", got, tt.want)
}
if got := twoSum2(tt.args.nums, tt.args.target); !reflect.DeepEqual(got, tt.want) {
t.Errorf("twoSum() = %v, want %v", got, tt.want)
}
},
)
}
}

测试结果

1
2
3
4
5
6
7
8
9
10
11
=== RUN   TestTwoSum
--- PASS: TestTwoSum (0.00s)
=== RUN TestTwoSum/01
--- PASS: TestTwoSum/01 (0.00s)
=== RUN TestTwoSum/02
--- PASS: TestTwoSum/02 (0.00s)
=== RUN TestTwoSum/03
--- PASS: TestTwoSum/03 (0.00s)
PASS

Process finished with exit code 0

总结

方法 时间复杂度 空间复杂度
暴力枚举 $O(n^2)$ $O(1)$
哈希表 $O(n)$ $O(n)$,主要是哈希表的开销
----- 到这结束咯 感谢您的阅读 -----