给定一个数组 nums 和一个目标值 target ,请问从 nums 中选出三个数,使其之和尽量接近目标数,即三数之和与目标数只差绝对值尽可能小。
返回满足题面要求的三数之和。
数据范围:数组长度满足 ,数组中的值满足 ,目标值满足 ,可以保证只有一个结果。
[-1,2,1,-4],1
2
最接近 1 的三数之和是 -1+2+1 = 2
[0,0,0],1
0
只有一种选择 0+0+0
[0,1,0,0],0
0
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @param target int整型
* @return int整型
*/
public int ClosestSum (int[] nums, int target) {
// write code here
int n = nums.length;
Arrays.sort(nums);
int res = nums[0] + nums[1] + nums[2];
for(int first = 0; first < n; first++){
int second = first + 1, third = n - 1;
while(second < third){
int tempSum = nums[first] + nums[second] + nums[third];
if(Math.abs(target - tempSum) < Math.abs(target - res)){
res = tempSum;
}
if(tempSum > target){
third--;
}else if(tempSum < target){
second++;
}else{
return res;
}
}
}
return res;
}
}
public static int resSum = Integer.MAX_VALUE; public int ClosestSum(int[] nums, int target) { // write code here boolean[] isUsed = new boolean[nums.length]; // 暴力全量收集 LinkedList<Integer> currList = new LinkedList<>(); recursiveHelper(nums, isUsed, currList, target); return resSum; } public static boolean recursiveHelper(int[] nums, boolean[] isUsed, LinkedList<Integer> currList, int target) { if (currList.size() == 3) { int sum = 0; for (Integer i : currList) sum += i; int currAbs = Math.abs(sum - target); // 表示找到最优解 if (currAbs == 0) { resSum = sum; return true; } int lastAbs = Math.abs(resSum - target); resSum = currAbs < lastAbs ? sum : resSum; return false; } int len = nums.length; for (int i = 0; i < len; i++) { if (isUsed[i]) continue; isUsed[i] = true; currList.addLast(nums[i]); boolean res = recursiveHelper(nums, isUsed, currList, target); if (res) return true; else { // 回溯,尝试其他 isUsed[i] = false; currList.removeLast(); } } return false; }
package main import "sort" import "math" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ func ClosestSum( nums []int , target int ) int { sort.Ints(nums) ans:=math.MaxInt32 for i:=0;i<len(nums);i++{ if i>0&&nums[i]==nums[i-1]{ continue } sum:=0 l,r:=i+1,len(nums)-1 for l<r{ sum=nums[i]+nums[l]+nums[r] if abs(sum,target)<abs(ans,target){ ans=sum } if sum==target{ return sum }else if sum>target{ r-- }else{ l++ } } } return ans } func abs(a,b int)int{ if a>b{ return a-b } return b-a }
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param numsLen int nums数组长度 * @param target int整型 * @return int整型 * * C语言声明定义全局变量请加上static,防止重复定义 */ #include<math.h> int cmp(const void*a,const void*b){ return(*(int*)a)-(*(int*)b); } int ClosestSum(int* nums, int numsLen, int target ) { qsort(nums,numsLen,sizeof(nums[0]),cmp); int i,j,k,sum,res; res=nums[0]+nums[1]+nums[2]; for(i=0;i<numsLen;i++){ j=i+1; k=numsLen-1; while(j<k){ sum=nums[i]+nums[j]+nums[k]; if(abs(sum-target)<abs(res-target)){ res=sum; } if(sum>target){ k--; } if(sum<target){ j++; } if(sum==target){ return sum; } } } return res; }
class Solution: def ClosestSum(self , nums: List[int], target: int) -> int: # write code here nums.sort() res = nums[0]+nums[1]+nums[2] for i in range(len(nums)-2): start, end = i+1, len(nums)-1 while start < end: tmp = nums[i]+nums[start]+nums[end] if abs(tmp-target) < abs(res-target): res = tmp if tmp > target: end -= 1 elif tmp < target: start += 1 else: return res return res
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int ClosestSum(vector<int>& nums, int target) { int n=nums.size(); sort(nums.begin(),nums.end()); int res=nums[0]+nums[1]+nums[2]; for(int i=0;i<n;i++){ if(i>0&&nums[i]==nums[i-1]){ continue; } int j=i+1,k=n-1; while(j<k){ int sum=nums[i]+nums[j]+nums[k]; if(abs(sum-target)<abs(res-target)){ res=sum; } if(res==target){ return target; }else if(sum>target){ k--; }else if(sum<target){ j++; } } } return res; } };
public class Solution { public int ClosestSum (int[] nums, int target) { Arrays.sort(nums); int min = Integer.MAX_VALUE, res = 0; for (int i = 0; i < nums.length-2; i++) { if (i > 0 && nums[i] == nums[i-1]) continue; int start = i + 1, end = nums.length-1, sum = 0, dif = 0; while (start < end) { sum = nums[i] + nums[start] + nums[end]; dif = Math.abs(sum-target); if (dif < min) { min = dif; res = sum; } if (sum > target) { end--; while (start < end && nums[end+1]== nums[end]) end--; } else if (sum < target) { start++; while (start < end && nums[start-1]== nums[start]) start++; } else return target; } } return res; } }