What is the core technique to solve 3Sum Closest?

The core technique involves sorting the array and using the two-pointer method to efficiently find a triplet that is closest to the target sum.

How do you minimize the difference between the sum and target?

You use two pointers to scan through the array, adjusting based on whether the current sum is too low or too high compared to the target.

What is the time complexity of this problem?

The time complexity is O(n^2) due to the two-pointer scanning for each element in the array after sorting it in O(n log n) time.

Can you handle arrays with negative numbers efficiently?

Yes, by sorting the array and applying the two-pointer technique, you can efficiently handle both negative and positive numbers while finding the closest sum.

Is there a more efficient solution than O(n^2) for this problem?

Currently, O(n^2) is the best achievable time complexity for solving this problem, as each number needs to be checked in combination with others.

#16

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

最接近的三数之和

给你一个长度为 n 的整数数组 nums 和一个目标值 target 。请你从 nums 中选出三个在不同下标位置的整数，使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。示例 1：输入： nums = [-1,2,1,-4], target = 1 …

数组双指针排序

题目描述

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个在 不同下标位置 的整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10⁴ <= target <= 10⁴

lightbulb

解题思路

方法一：排序 + 双指针

我们将数组排序，然后遍历数组，对于每个元素 $nums[i]$ ，我们使用指针 $j$ 和 $k$ 分别指向 $i+1$ 和 $n-1$ ，计算三数之和，如果三数之和等于 $target$ ，则直接返回 $target$ ，否则根据与 $target$ 的差值更新答案。如果三数之和大于 $target$ ，则将 $k$ 向左移动一位，否则将 $j$ 向右移动一位。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(\log n)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        ans = inf
        for i, v in enumerate(nums):
            j, k = i + 1, n - 1
            while j < k:
                t = v + nums[j] + nums[k]
                if t == target:
                    return t
                if abs(t - target) < abs(ans - target):
                    ans = t
                if t > target:
                    k -= 1
                else:
                    j += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you know how to handle cases where the array has both negative and positive numbers?
question_mark
Can you explain the two-pointer strategy and how it minimizes the difference to the target?
question_mark
Will you discuss the trade-offs between time complexity and the accuracy of finding the closest sum?

warning

常见陷阱

外企场景

error
Forgetting to sort the array first, which can lead to inefficient solutions or missed results.
error
Not properly managing pointer updates, potentially leading to incorrect triplets being selected.
error
Overlooking edge cases such as when all numbers in the array are equal or when the target is very far from all possible sums.

swap_horiz

进阶变体

外企场景

arrow_right_alt
3Sum problem, where you find an exact target sum with three numbers.
arrow_right_alt
4Sum Closest problem, where you find four integers that sum closest to a given target.
arrow_right_alt
3Sum with Multiplicity, where you find the number of distinct triplets that sum to the target.

help

常见问题

外企场景

继续练习

#15 三数之和 #18 四数之和 #75 颜色分类