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

問題：

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

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

入力された整数の順序がバラバラなのでまずはソートする事をお勧めします。
私の答えはO(n^2)なのでソートしてもTime Complexityへの影響はないですが、
もしO(n*logn)以下の回答がある場合はソートがボトルネックとなってしまうので避けましょう。

注意すべき事:　

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

以下回答です。

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

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

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