給定一個包括?n 個整數(shù)的數(shù)組?nums?和 一個目標(biāo)值?target。找出?nums?中的三個整數(shù)，使得它們的和與?target?最接近。返回這三個數(shù)的和。假定每組輸入只存在唯一答案。

例如，給定數(shù)組 nums = [-1，2，1，-4], 和 target = 1.

與 target 最接近的三個數(shù)的和為 2. (-1 + 2 + 1 = 2).

思路：

雙指針法

本題中并沒有說是連續(xù)的三個數(shù)字，所以在數(shù)組中任取三個數(shù)，使其與target最為接近即可

可以取兩個指針start,end

先將數(shù)組排序

每次遍歷的第一個數(shù)的位置為i，后面的兩個值在start與end之間依次尋找

在數(shù)組 nums 中，進行遍歷，每遍歷一個值利用其下標(biāo)i，形成一個固定值 nums[i]
再使用前指針指向 start = i + 1 處，后指針指向 end = nums.length - 1 處，也就是結(jié)尾處
根據(jù) sum = nums[i] + nums[start] + nums[end] 的結(jié)果，判斷 sum 與目標(biāo) target 的距離，如果更近則更新結(jié)果t
同時判斷 sum 與 target 的大小關(guān)系，因為數(shù)組有序，如果 sum > target 則 end--，如果 sum < target 則 start++，如果 sum == target 則說明距離為 0 直接返回結(jié)果

提交的代碼：

class Solution {
? ? public int threeSumClosest(int[] nums, int target) {
? ? ? ? ? Arrays.sort(nums);
?? ??? ? int i=0,start,end;
?? ??? ? int sum = nums[0]+nums[1]+nums[2];
?? ??? ? int min = Math.abs(sum-target);
?? ??? ? int t = sum;
?? ??? ? for(i=0;i<nums.length-2;i++)
?? ??? ? {
?? ??? ??? ? start=i+1;
?? ??? ??? ? end = nums.length-1;
?? ??? ??? ? while(start<end)
?? ??? ??? ? {
?? ??? ??? ??? ? sum = nums[start]+nums[i]+nums[end];
?? ??? ??? ??? ? if(min>Math.abs(sum-target))
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? min=Math.abs(sum-target);
?? ??? ??? ??? ??? ? t = sum;
?? ??? ??? ??? ? }
?? ??? ??? ??? ? if(sum>target)
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? end-=1;
?? ??? ??? ??? ? }
?? ??? ??? ??? ? else if(sum<target)
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? start+=1;
?? ??? ??? ??? ? }
?? ??? ??? ??? ? else
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? return t;
?? ??? ??? ??? ? }
?? ??? ??? ? }
?? ??? ? }
?? ??? ? return t;
? ? }
}

完整的代碼：

import java.util.Arrays;

public class Solution16 {
?? ? public static int threeSumClosest(int[] nums, int target) {
?? ??? ? Arrays.sort(nums);
?? ??? ? int i=0,start,end;
?? ??? ? int sum = nums[0]+nums[1]+nums[2];
?? ??? ? int min = Math.abs(sum-target);
?? ??? ? int t = sum;
?? ??? ? for(i=0;i<nums.length-2;i++)
?? ??? ? {
?? ??? ??? ? start=i+1;
?? ??? ??? ? end = nums.length-1;
?? ??? ??? ? while(start<end)
?? ??? ??? ? {
?? ??? ??? ??? ? sum = nums[start]+nums[i]+nums[end];
?? ??? ??? ??? ? if(min>Math.abs(sum-target))
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? min=Math.abs(sum-target);
?? ??? ??? ??? ??? ? t = sum;
?? ??? ??? ??? ? }
?? ??? ??? ??? ? if(sum>target)
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? end-=1;
?? ??? ??? ??? ? }
?? ??? ??? ??? ? else if(sum<target)
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? start+=1;
?? ??? ??? ??? ? }
?? ??? ??? ??? ? else
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? return t;
?? ??? ??? ??? ? }
?? ??? ??? ? }
?? ??? ? }
?? ??? ? return t;
?? ? ? ?}
?? ? public static void main(String[] args)
?? ? {
?? ??? ? int[] nums = {-1,2,1,-4};
?? ??? ? int target = 1;
?? ??? ? System.out.println(threeSumClosest(nums,target));
?? ? }
}
?

?

總結(jié)

以上是生活随笔為你收集整理的Leetcode--16. 最接近的三数之和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。