首页 > 试题广场 >

最接近的三数之和

[编程题]最接近的三数之和

热度指数：12787 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出含有n个整数的数组s，找出s中和加起来的和最接近给定的目标值的三个整数。返回这三个整数的和。你可以假设每个输入都只有唯一解。

   例如，给定的整数 S = {-10 20 10 -40}, 目标值 = 10.
   最接近目标值的和为 2. (-10 + 20 + 10 = 20).

示例1

输入

[0,0,0],1

输出

算法知识视频讲解

Java

HW柯可

import java.util.Arrays;
import java.util.ArrayList;

public class Solution {
    ArrayList<Integer> res_list;
    int sum = 0;
    int close_temp = Integer.MAX_VALUE;
    public int threeSumClosest(int[] num, int target) {
        ArrayList<Integer> list =  new ArrayList<>();
        combine(num, target, 0, list);
        
        int result = 0;
        for(int i = 0; i < res_list.size(); i++){
            result += res_list.get(i);
        }
        return result;
    }
    //回溯法
    public void combine(int[] num, int target, int start, ArrayList<Integer> list){
        if(list.size() == 3 ){
            if(Math.abs(sum - target) < close_temp){
                close_temp = Math.abs(sum - target);
                res_list = new ArrayList<>(list);
            }
            return;
        }
            for(int i = start; i < num.length; i++){
                sum += num[i];
                list.add(num[i]);
                combine(num, target, i + 1, list);
                sum -= list.get(list.size()-1);
                list.remove(list.size()-1);
            }
    }
}

编辑于 2020-07-16 16:50:43 回复(0)

Java

jRomann

import java.util.*;
public class Solution {
public int threeSumClosest(int[] num, int target) {
int min = Integer.MAX_VALUE;
int res =0;
for(int i=0;i<num.length-2;i++){
for(int j=i+1;j<num.length-1;j++){
for(int m = j+1;m<num.length;m++){
int sum=num[i]+num[j]+num[m];
if(Math.abs(sum-target)<min){
min =Math.abs(sum-target);
res = sum;
}

}
}
}
return res;
}
}

发表于 2018-07-11 16:46:58 回复(0)

Java

詆調壹點

public class Solution {
    public int threeSumClosest(int[] num, int target) {
		int sum = 0, error = 0, result = 0, min = Integer.MAX_VALUE;
		for (int i = 0; i < num.length; i ++) {
			for (int j = i + 1; j < num.length; j ++) {
				for (int k = j + 1; k < num.length; k ++) {
					sum = num[i] + num[j] + num[k];
					error = Math.abs(sum - target);
					if(error == 0) return sum;
					if(error < min) {
						min = error;
						result = sum;
					}
				}
			}
		}
		return result;
	}
}

发表于 2017-03-24 22:21:21 回复(3)

Java

城市里的养猫者

Similar to 3 Sum problem, use 3 pointers to point current element, next element and the last element. If the sum is less than target, it means we have to add a larger element so next element move to the next. If the sum is greater, it means we have to add a smaller element so last element move to the second last element. Keep doing this until the end. Each time compare the difference between sum and target, if it is less than minimum difference so far, then replace result with it, otherwise keep iterating.

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