两数之和，三数之和

Posted on Edited on In Word count in article: 2.9k Reading time ≈ 3 mins.
两数之和，三数之和

两数之和

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

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

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

1
2
input = [2,7,11,15], target = 9
res = [0,1]

暴力解法

注意不能用重复元素，要判断i！=j的条件

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

两重for循环，o(n方)

map解法

建立一个map，循环这个数组，判断target-i在不在这个map里，不在就把这个i和其索引放到map里

如果后续有新的i能跟此次循环的i，target-i在这个map里就返回，找到了

重复的数字，索引覆盖即可，也避免了使用同一

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    numsMap := make(map[int]int, len(nums))
    for p, num := range nums {
        if q, ok := numsMap[target - num]; ok {
            return []int{q, p}
        }
        numsMap[num] = p
    }
    return []int{}
}

只需循环遍历一次， O(n)

三数之和

相比于2数之和，加了一阶

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

暴力解法三重循环

三重遍历，O(n三次方)

去除重复，先排序

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
50
51
52
func threeSum(nums []int) [][]int {

	// 排序，遇到相同的可以跳过循环

    for i:= 0 ;i<len(nums);i++{
        for j := 0 ;j<len(nums);j++{
            if nums[i]>nums[j]{
                nums[i],nums[j] = nums[j],nums[i]
            }
        }
    }

	n := 0;
	num := make([][]int,0,0)
	// 开始遍历
	for i:= 0 ; i<len(nums) ;i++{
		// 重复的就跳过，下一位
        if i>=1 && nums[i-1] == nums[i]{
            continue
        }
        // 计数
        n += nums[i]
		for j := i+1 ; j<len(nums) ;j++{
			// 第二层遍历，重复的跳过
            if j>=i+2 && nums[j-1] == nums[j]{
                continue
            }
             // 计数
            n += nums[j]
			for k:= j+1 ;k<len(nums) ;k++{
				// 第三层遍历，重复的跳过
                if k>=j+2 && nums[k-1] == nums[k]{
                    continue
                }
                // 计数，n是三个数之和，如果为0，则是结果保存
                n += nums[k]
				if n==0{
                    t := []int{nums[i],nums[j],nums[k]}
					num = append(num,t)
				}
				// 如果不是，减去k
				n -= nums[k]
			}
			// 再减去j
			n -= nums[j]
		}
		// 减去i
		n -= nums[i]
	}
	return num
}

会超出时间限制

双指针夹逼

将数组排序，固定一个指针，然后剩下的两个指针一个在头，一个在尾，往中间移动

1

现在已经找到了三个数，当然是计算其三值是否满足三元组。但是这里因为我们已经排好了序，如果固定下来的数（上面蓝色框框）本身就大于0，那三数之和必然无法等于0

我们需要移动指针。现在我们的排序就发挥出用处了，如果和大于 0，那就说明 right 的值太大，需要左移。如果和小于 0，那就说明 left 的值太小，需要右移

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
50
51
52
53
func threeSum(nums []int) [][]int {
	// 先从小到大排序
	sort.Ints(nums)
	// 接收结果
	var res [][]int
	// 获取数组长度
	length := len(nums)
	// 边界处理，数字不足三个直接返回空
	if len(nums) < 3 {
		return res
	}
	// 开始循环第一个固定值
	for index, value := range nums {
		// 如果固定位的值已经大于0，因为已经排好序了，后面的两个指针对应的值也肯定大于0，则和不可能为0，所以返回
		if nums[index] > 0 {
			return res
		}
		// 排除值重复的固定位
		if index > 0 && nums[index] == nums[index-1] {
			continue
		}
		// 指针初始位置，固定位右边第一个和数组最后一个
		l := index + 1
		r := length - 1
		// 开始移动两个指针
		for l < r {
			// 判断三个数字之和的三种情况
			sum := value + nums[l] + nums[r]
			switch {
			case sum == 0:
				// 将结果加入二元组
				res = append(res, []int{nums[index], nums[l], nums[r]})
				// 去重，如果l < r且下一个数字一样，则继续挪动
				for l < r && nums[l] == nums[l+1] {
					l += 1
				}
				// 同理
				for l < r && nums[r] == nums[r-1] {
					r -= 1
				}
				l += 1
				r -= 1
			case sum > 0:
				// 如果和大于 0，那就说明 right 的值太大，需要左移
				r -= 1
				// 如果和小于 0，那就说明 left 的值太小，需要右移 
			case sum < 0:
				l += 1
			}
		}
	}
	return res
}