leetcode - 16. 最接近的三数之和

2024-04-13 14:58

文章标签 leetcode 16 三数接近

本文主要是介绍leetcode - 16. 最接近的三数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode - 16. 最接近的三数之和

题目大意

给定一个数组，要求在这个数组中找出 3 个数之和离 target 最近。

解题思路

这一题看似和第 15 题和第 18 题很像，都是求 3 或者 4 个数之和的问题，但是这一题的做法和 15，18 题完全不同。

这一题的解法是用两个指针夹逼的方法。先对数组进行排序，i 从头开始往后面扫。这里同样需要注意数组中存在多个重复数字的问题。具体处理方法很多，可以用 map 计数去重。这里笔者简单的处理，i 在循环的时候和前一个数进行比较，如果相等，i 继续往后移，直到移到下一个和前一个数字不同的位置。j，k 两个指针开始一前一后夹逼。j 为 i 的下一个数字，k 为数组最后一个数字，由于经过排序，所以 k 的数字最大。j 往后移动，k 往前移动，逐渐夹逼出最接近 target 的值。

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define INT_MAX 2147483647int threeSumClosest(vector<int> &num,int target)
{//对数组进行排序sort(num.begin(),num.end());int n = num.size();int distance = INT_MAX;int result;for(int i = 0;i<n-2;i++){//跳过重复if(i > 0 && num[i - 1] == num[i]) continue;int a = num[i];int low = i + 1;int high = n - 1;//将3sum转化为2sum问题while(low < high){int b = num[low];int c = num[high];int sum = a + b + c;if(sum - target == 0){//得到最终解决方案return target;}else{//跟踪最小距离if(abs(sum - target) < distance){distance = abs(sum - target);result = sum;}if(sum - target > 0){//跳过重复while(high > 0 && num[high] == num[high - 1]) high--;//移动`high`指针high--;}else{//跳过重复while(low < n && num[low] == num[low + 1]) low++;//移动`low`指针low--;}}}}return result;
}int main()
{int a[] = {-1,2,1,-4};vector<int> n(a,a+sizeof(a)/sizeof(int));int target = 1;cout<<threeSumClosest(n,target)<<endl;return 0;
}