LeetCode #18. 4Sum プログラミング練習

問題：

難易度:　medium
入力:　int型Array
目的: 入力された整数の内、和がtargetになる四つの整数の組み合わせをすべて出力せよ
出力:　int型リストのリスト

#15の3Sumの延長問題です。
基本思想は全く同じで、♯15を解けた人なら同じ方法で解けると思います。
入力された整数の順序がバラバラなのでまずはソートする事をお勧めします。
私の答えはO(n^3)なのでソートしてもTime Complexityへの影響はないですが、
もしO(n*logn)以下の回答がある場合はソートがボトルネックとなってしまうので避けましょう。

注意すべき事:　

• テストケースによっては重複した答えが多数存在するのでスキップすること

以下回答です。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int len = nums.length;
        if (len<4) return result;
        for (int i=0; i<len; i++) {
            for (int j=i+1; j<len; j++) {
                    int left = j+1;
                    int right = len-1;
                while (left < right) {
                    int res = nums[i] + nums[j] + nums[left]+ nums[right];
                    if (res == target) {
                        List<Integer> ans = new ArrayList<Integer>();
                        ans.add(nums[i]);
                        ans.add(nums[j]);
                        ans.add(nums[left]);
                        ans.add(nums[right]);
                        result.add(ans);
                        while (i+1<len && nums[i] == nums[i+1]) i++;
                        while (j+1<len && nums[j] == nums[j+1]) j++;
                        while (left+1<len && nums[left] == nums[left+1]) left++;
                        while (right-1>0 && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }
                    if (res - target < 0) left++;
                    if (res - target > 0) right--;
                }
            }
        }
        return result;
    }
}

まず入力されたArrayをソートします。
ソートされたArrayをForでまわします。
i番目の数字を固定し、右側から和がtargetになる対象数字を探します。
3Sumとの唯一の違いは固定する数字が二つある事です。
leftとrightポインタを用意し、leftはi+1の数字から、rightは最後尾から。
和がtarget以上だったらright--,以下だったらleft++を繰り返します。
対象の組み合わせを見つけた場合はresにリストを追加していきます。
最後に重複を防ぐ為に同じ数字はスキップしておきます。
Time ComplexityはO(n^3)です。

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