【leetcode】_3sum_closest

• 思路
  • 2sum的基础上外加一层循环，用于遍历第1~n-2的n-2个数
  • 首先对num数组进行排序
  • 从第二个数j和最后一个数k开始向中间夹逼
  • 如果遇到两个相等的数向下一个移动
  • 维护一个minus数用于表示sum和target的差值
  • 如果等于0，那么返回target
  • 如果小于0，j++
  • 如果大于0，k--
  • 另外维护一个dis=minus的绝对值
  • 如果每一次遍历使得dis变小，那么将新的sum赋值给ret

    ? ?

    package leetcode.doit;

    import java.util.Arrays;

    ? ?

    /**

    * 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).

    *

    */

    public class ThreeSumClosest {

    public int threeSumClosest(int[] num, int target) {

    int dis = Integer.MAX_VALUE;

    int ret = 0;

    Arrays.sort(num);

    int length = num.length;

    for (int i = 0; i < length - 2; i++) {

    int j = i + 1;

    int k = length - 1;

    while (j < k) {

    if (j > i + 1 && num[j] == num[j - 1]) {

    j++;

    continue;

    }

    if (k < length - 1 && num[k] == num[k + 1]) {

    k--;

    continue;

    }

    int sum = num[i] + num[j] + num[k];

    int minus = sum - target;

    int d = Math.abs(minus);

    if (d < dis) {

    dis = d;

    ret = sum;

    }

    if (minus == 0)

    return target;

    if (minus < 0) {

    j++;

    } else {

    k--;

    }

    }

    }

    return ret;

    }

    }

    ? ?

【leetcode】_3sum_closest

原文：http://www.cnblogs.com/keedor/p/4366744.html