专栏首页leetcode_solutions【每天一道编程系列-2018.3.7】(Ans)

【每天一道编程系列-2018.3.7】(Ans)

【题目描述】

  Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.    For example, given array S = {-1 2 1 -4}, and target = 1.    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). 

【题目大意】

给定包含n个整数数组S,找到S中的三个整数,从而使之和最接近给定的数。返回三个整数的总和。你可以假设每个输入将有一个确切的解决。 

【本题答案】

package blog;

import java.util.Arrays;

/**
 * @author yesr
 * @create 2018-03-07 下午11:45
 * @desc
 **/
public class Test0307 {
    public int threeSumClosest(int[] nums, int target) {

        // 记录最小的差值
        long minDiff = Long.MAX_VALUE;
        // 记录最小差值对应的三个整数和
        long result = 0;
        // 每次求得的差值
        long diff;
        // 每次求得的三个整数的和
        long sum;

        // 先对数组进行排序
        Arrays.sort(nums);


        // i表示假设取第i个数作为结果
        for (int i = 0; i < nums.length - 2; i++) {
            // 第二个数可能的起始位置
            int j = i + 1;
            // 第三个数可能是结束位置
            int k = nums.length - 1;

            while (j < k) {
                // 求当前三个数的和
                sum = nums[j] + nums[k] + nums[i];
                // 当前和与目标和之间的差值
                diff = Math.abs(target - sum);

                // 差值为0就直接返回
                if (diff == 0) {
                    return (int) sum;
                }

                // 如果当前的差值比之前记录的差值小
                if (diff < minDiff) {
                    // 更新最小的差值
                    minDiff = diff;
                    // 更新最小差值对应的和
                    result = sum;

                    // 以上的设置在下一次元素处理时生效
                }


                // 和大于target
                if (sum > target) {
                    k--;
                }
                // 和小于target
                else {
                    j++;
                }
            }
        }

        return (int) result;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1. Two Sum(HashMap储存数组的值和索引)

    Given an array of integers, return indices of the two numbers such that they add...

    yesr
  • 26. Remove Duplicates from Sorted Array

    Given a sorted array nums, remove the duplicates in-place such that each element...

    yesr
  • 【每天一道编程系列-2018.3.6】(Ans)

    Given an array S of n integers, are there elements a, b, c in S such that a + b ...

    yesr
  • LeetCode 525. 连续数组(前缀和+哈希)

    给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组(的长度)。

    Michael阿明
  • leetcode 26 Remove Duplicates from Sorted Array

    Remove Duplicates from Sorted ArrayTotal Accepted: 66627 Total Submissions: 2127...

    流川疯
  • O(n)时间的排序

    题目:某公司有几万名员工,请完成一个时间复杂度为O(n)的算法对该公司员工的年龄作排序,可使用O(1)的辅助空间。      题目特别强调是对一个公司的员工的年...

    猿人谷
  • 【LeetCode】两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

    弗兰克的猫
  • 【LeetCode】两数之和

    Jacob丶
  • 查找数组中两数之和等于指定的数

    题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    Melody132
  • leetcode 27 Remove Element

    Remove Element Total Accepted: 60351 Total Submissions: 187833 My Submissio...

    流川疯

扫码关注云+社区

领取腾讯云代金券