美文网首页
每天一题LeetCode【第14天】

每天一题LeetCode【第14天】

作者: 草稿纸反面 | 来源:发表于2017-02-03 00:00 被阅读332次

    T16. 3Sum Closest【Medium

    题目

    给一个有 n 个整数的数组 S,找到 S 中的三个数,使得这三个数的和最接近传入的target(目标数)。并返回这三个数的 sum(和)。你何以假设每个输入都有一个确切的解答。

    举个例子,如果给出数组 S = [-1, 2, 1, -4],并且 target(目标数) = 1
    
    最接近的 sum 是 2.(-1 + 2 + 1 = 2)
    
    

    思路

    具体可以看代码注释~

    代码

    代码取自 Top Solution,稍作注释

     public int threeSumClosest(int[] num, int target) {
            //初始一个result
            int result = num[0] + num[1] + num[num.length - 1];
            //给num排序
            Arrays.sort(num);
            for (int i = 0; i < num.length - 2; i++) {
                int start = i + 1, end = num.length - 1;
                //在while中num[i]是一定的,选出的是i时,i后面的数和i能组成的离target最近的sum
                while (start < end) {
                    int sum = num[i] + num[start] + num[end];
                    //sum>target要减小sum,因为排好序了,所以end--
                    if (sum > target) {
                        end--;
                    } else {       //sum<=target时同理
                        start++;
                    }
                    //若相差小,则更新result值
                    if (Math.abs(sum - target) < Math.abs(result - target)) {
                        result = sum;
                    }
                }
            }
            return result;
        }
    

    补充

    这题发现当从数组里面挑选数相加为一个目标数是时,可以用先把数组排序,从两边往里相加凑数这样的方法。

    之前写的类似的解法:T15 3Sum

    相关文章

      网友评论

          本文标题:每天一题LeetCode【第14天】

          本文链接:https://www.haomeiwen.com/subject/rxorittx.html