B29052970f6c14be70919f5814bc8372
(难度Medium)Problem 16: 3Sum-closest

Problem 16: 3Sum-closest

链接

链接:https://leetcode.com/problems/3sum-closest/

难度等级

Medium

题干

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

题意

和上一题非常近似,给定一个无序的数组,和一个目标target,要求从数组当中找到三个数:a,b,c使得a+b+c和target尽可能接近,最后返回a+b+c的和。

样例

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

题解

这道题和上一题3Sum基本一致,可以直接沿用3Sum的解法来解决。

我们首先对数组进行排序,保证数组从小到大有序。接着,我们枚举a,b,c这三个数当中的最小值。假设,我们取了数组中的第i位。那么b,c的范围只可能是[i+1, n)。我们只需要在这个区间里跑一下two pointers即可。

我们新建两个指针l, r,分别指向这个区间的头尾。如果a[i] + a[l] + a[r] > target,说明r位置的数取得太大了,可以往左移,如果a[i] + a[l] + a[r] < target,说明l的位置取得太小了,需要往右移。只要我们不断调整l和r的位置,记录下移动过程当中所达到的和target最接近的数即可。

我们遍历i的位置,复杂度是$O(n)$,由于l和r最多只能移动n次,所以双指针得移动操作复杂度也是$O(n)$,两者相乘的复杂度是$O(n^2)$。

代码

```
class Solution {
public:
int threeSumClosest(vector& nums, int target) {
sort(nums.begin(), nums.end());

top Created with Sketch.