LeetCode 16. 最接近的三数之和

题目描述

🔥 16. 最接近的三数之和

image-20241020131300538

思路分析

我们可以使用排序加双指针的方法来解决这个问题。具体思路如下：

  1. 首先对数组 nums 进行排序。
  2. 遍历数组，固定一个数 nums[i]，然后使用双指针来查找另外两个数。
  3. 初始化两个指针，left 指向 i + 1，right 指向数组的末尾。
  4. 计算三数之和 sum = nums[i] + nums[left] + nums[right]：
    • 如果 sum 等于 target，直接返回 sum。
    • 如果 sum 小于 target，说明需要更大的和，将 left 向右移动。
    • 如果 sum 大于 target，说明需要更小的和，将 right 向左移动。
  5. 在每次计算中，更新最接近的和 closest。
  6. 重复以上步骤，直到遍历完所有元素。

参考代码

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

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)

	// 初始化最接近的和
	closest := nums[0] + nums[1] + nums[2]

	for i := 0; i < len(nums)-2; i++ {
		left, right := i+1, len(nums)-1

		for left < right {
			sum := nums[i] + nums[left] + nums[right]

			// 更新最接近的和
			if abs(sum-target) < abs(closest-target) {
				closest = sum
			}

			if sum < target {
				left++
			} else if sum > target {
				right--
			} else {
				return sum
			}
		}
	}

	return closest
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}
  • 时间复杂度：O (n^2)，其中 n 是数组 nums 的长度。我们需要对数组进行排序，之后再进行双指针查找。
  • 空间复杂度：O (1)，只使用了常数级别的额外空间。

🍏 点击查看 Java 题解

1

write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2022/93653913
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！