leetCode-4Sum(two pointer)

문제

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

 

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8 Output: [[2,2,2,2]]

 

Constraints:

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

 

---

풀이

1. 첫번째 풀이

const fourSum = function (nums, target) {
    let result = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            let low = j + 1, high = nums.length - 1, sum = 0;

            while (low < high) {
                sum = nums[i] + nums[j] + nums[low] + nums[high];
                if (sum === target) {
                    result.push([nums[i], nums[j], nums[low], nums[high]]);
                    low++
                } else if (sum < target) {
                    while (nums[low] === nums[low + 1]) low++;
                    low++
                } else if (sum > target) {
                    while (nums[high] === nums[high - 1]) high--;
                    high--;
                }

            }
        }
    }

    return [...new Set(result.map(JSON.stringify))].map(JSON.parse);

};

위 방식으로 문제를 해결하면 시간초과가 발생한다.

 

2. 두번째 풀이 방식

const fourSum = function (nums, target) {
    let result = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            let low = j + 1, high = nums.length - 1, sum = 0;

            while (low < high) {
                sum = nums[i] + nums[j] + nums[low] + nums[high];
                if (sum === target) {
                    result.push([nums[i], nums[j], nums[low], nums[high]]);
                    while (nums[low] === nums[low + 1]) low++;
                    low++
                } else if (sum < target) {
                    while (nums[low] === nums[low + 1]) low++;
                    low++
                } else if (sum > target) {
                    while (nums[high] === nums[high - 1]) high--;
                    high--;
                }
            }
            while (nums[j] === nums[j + 1]) j++;
        }
        while (nums[i] === nums[i + 1]) i++;
    }

    return result;

};

문제에서 중복되는 요소의 값이 없다고 했기 때문에, 각각의 for문에서 현재 인덱스 값과 다음 인덱스의 값이 같아면 index를 하나씩 올려주는 방식이다.