leetcode [15]

배열의 3가지 합이 0이 되어야 함
동시에 같은 원소가 들어가면 안된다
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

처음엔 sort를 사용하지 않고, 투포인터로 풀어냈으나 시간 복잡도가 O(n^3)로 되어 어떻게 해도 낮아 지지 않았다

정렬되지 않은 배열을 투포인터로 한다고 하면 무차별 대입으로 할 수 밖에 없기 때문이다

그리고 중간에 while문이 두개가 들어가는데, 중복값을 건너 뛰기 위한 부분이다

중복값을 없애지 않으면 투포인터가 교차되기 때문에 같은 결과 값을 또 집어넣는 경우가 생긴다

var threeSum = function(nums) {
    nums.sort((a, b) => a - b);
    let final = [];

    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) {
            continue;
        }
        let l = i + 1;
        let r = nums.length - 1;

        while (l < r) {
            let sum = nums[i] + nums[l] + nums[r];
            if (sum === 0) {
                final.push([nums[i], nums[l], nums[r]]);
                while (nums[l] === nums[l + 1]) {
                    l++;
                }
                while (nums[r] === nums[r - 1]) {
                    r--;
                }
                l++;
                r--;
            } else if (sum < 0) {
                l++;
            } else if (sum > 0) {
                r--;
            }
        }
    }
    return final;
};