[LeetCode] 18. 4Sum

https://leetcode.com/

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
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

 

Code :

var fourSum = function(nums, target) {
    let result = new Array(); // 결과를 담을 배열을 선언합니다.
    let check = new Array(); // 중복을 확인하기 위한 배열을 선언합니다.

    nums.sort((a, b) => {return a - b}); // 입력 배열을 오름차순으로 정렬합니다.

    for (let i = 0; i < nums.length-3; i++) { // 첫 번째 수를 기준으로 루프를 돌립니다.
        let newTarget = target - nums[i]; // 새로운 타겟을 계산합니다.
        for (let j = i+1; j < nums.length-2; j++) { // 두 번째 수를 기준으로 루프를 돌립니다.
            let left = j+1; // 왼쪽 포인터를 초기화합니다.
            let right = nums.length-1; // 오른쪽 포인터를 초기화합니다.
            while (left < right) { // 왼쪽 포인터가 오른쪽 포인터보다 작은 동안
                if (nums[j] + nums[left] + nums[right] === newTarget) { // 세 수의 합이 새로운 타겟과 같다면
                    let temp = [nums[i], nums[j], nums[left], nums[right]]; // 임시 배열을 만듭니다.
                    if (check.indexOf(temp.toString()) == -1) { // 중복된 배열이 아니라면
                        check.push(temp.toString()); // 중복 배열에 추가합니다.
                        result.push(temp); // 결과 배열에 추가합니다.
                    }
                    left++; // 왼쪽 포인터를 증가시킵니다.
                    right--; // 오른쪽 포인터를 감소시킵니다.
                } else if (nums[j] + nums[left] + nums[right] < newTarget) { // 세 수의 합이 새로운 타겟보다 작다면
                    left++; // 왼쪽 포인터를 증가시킵니다.
                } else { // 세 수의 합이 새로운 타겟보다 크다면
                    right--; // 오른쪽 포인터를 감소시킵니다.
                }
            }
        }
    }
    return result; // 결과 배열을 반환합니다.
};

 

Solutions Code :

var fourSum = function(nums, target) {
  nums.sort((a, b) => a - b); // 배열을 정렬합니다.
  const quadruplets = []; // 결과 배열을 선언합니다.
  const n = nums.length; // 배열의 길이를 저장합니다.
  for (let i = 0; i < n - 3; i++) { // 첫 번째 수를 기준으로 루프를 돌립니다.
    if (i > 0 && nums[i] === nums[i - 1]) { // 중복된 요소는 건너뜁니다.
      continue;
    }
    for (let j = i + 1; j < n - 2; j++) { // 두 번째 수를 기준으로 루프를 돌립니다.
      if (j > i + 1 && nums[j] === nums[j - 1]) { // 중복된 요소는 건너뜁니다.
        continue;
      }
      let left = j + 1; // 왼쪽 포인터를 초기화합니다.
      let right = n - 1; // 오른쪽 포인터를 초기화합니다.
      while (left < right) { // 왼쪽 포인터가 오른쪽 포인터보다 작은 동안
        const sum = BigInt(nums[i]) + BigInt(nums[j]) + BigInt(nums[left]) + BigInt(nums[right]); // 네 수의 합을 계산합니다.
        if (sum < target) { // 합이 타겟보다 작다면
          left++; // 왼쪽 포인터를 증가시킵니다.
        } else if (sum > target) { // 합이 타겟보다 크다면
          right--; // 오른쪽 포인터를 감소시킵니다.
        } else { // 합이 타겟과 같다면
          quadruplets.push([nums[i], nums[j], nums[left], nums[right]]); // 결과 배열에 추가합니다.
          while (left < right && nums[left] === nums[left + 1]) { // 중복된 요소는 건너뜁니다.
            left++;
          }
          while (left < right && nums[right] === nums[right - 1]) { // 중복된 요소는 건너뜁니다.
            right--;
          }
          left++; // 왼쪽 포인터를 증가시킵니다.
          right--; // 오른쪽 포인터를 감소시킵니다.
        }
      }
    }
  }
  return quadruplets; // 결과 배열을 반환합니다.
};

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode