16. 最接近的三数之和-dfs-中等难度

问题描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest

题解

//dfs竟然过了
class Solution {
    int min, res;
    public void dfs(Stack<Integer> temp, int len, int[] nums, int size, int deep, int target){
        if(size == deep || len >=3){
            if(len == 3){
                int t = Math.abs(temp.get(0)+temp.get(1)+temp.get(2) - target);
                if(min > t){
                    min = t;
                    res = temp.get(0)+temp.get(1)+temp.get(2);
                }
            }
            return;
        }
        if(min == 0)return;
        temp.push(nums[deep]);
        dfs(temp, len+1, nums, size, deep+1, target);
        temp.pop();

        dfs(temp, len, nums, size, deep+1, target);
    }
    public int threeSumClosest(int[] nums, int target) {
        min = 10000000;
        res = 0;
        dfs(new Stack<Integer>(), 0, nums, nums.length, 0, target);
        return res;
    }
}