LeetCode #16. 3Sum Closest プログラミング練習

問題：

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

難易度:　medium
入力:　int型Array
目的: 入力された整数の内、和がターゲットに最も近い三つの整数の和を出力せよ
出力:　int

入力された整数の順序がバラバラなのでまずはソートする事をお勧めします。
私の答えはO(n^2)なのでソートしてもTime Complexityへの影響はないですが、
もしO(n*logn)以下の回答がある場合はソートがボトルネックとなってしまうので避けましょう。
前の♯15と殆ど同じで、しかも重複等を考えないでいいのでむしろ簡単になっています。

注意すべき事:　

• result変数を初期化する時Integer.MAX_VALUEに設定してしまうと、targetがマイナスの時オーバーフローしてしまうので適当な大きな数字にするかオーバーフローの時の処理を考えなければなりません。

以下回答です。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int len = nums.length;
        int res = 1000000;
        Arrays.sort(nums);
        for (int i=0; i<len; i++) {
            int right = len-1;
            int left = i+1;
            while (left < right) {
                if (Math.abs(nums[i] + nums[left] + nums[right] - target) < Math.abs(res - target)) {
                    res = nums[i] + nums[left] + nums[right];
                }
                if (nums[i] + nums[left] + nums[right] - target < 0) left++;
                else if (nums[i] + nums[left] + nums[right] - target > 0) right--;
                else return res;
            }
        }
        return res;
    }
}

まず入力されたArrayをソートします。
ソートされたArrayをForでまわします。
非正数である場合はi番目の数字を固定し、右側から和とtargetとの差が小さい組み合わせを探します。
leftとrightポインタを用意し、leftはi+1の数字から、rightは最後尾から。
和が0以上だったらright--,以下だったらleft++を繰り返します。
一番小さい和をresに格納し毎回比較し更新していきます。
Time ComplexityはO(n^2)です。

今日は以上。
よいプログラミング生活を！