Zayden

leetcode - 3Sum

July 31, 2023

문제 설명

정수 배열 nums가 주어졌을 때, i != j, i != k, j != k, nums[i] + nums[j] + nums[k] == 0이 되도록 모든 삼중 항 [nums[i], nums[j], nums[k]]을 반환합니다.

솔루션 집합에 중복된 삼중항이 포함되어서는 안됩니다.

  • 예시 1
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.
  • 예시 2
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
  • 예시 3
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

제약 조건:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

문제 접근

입력받은 배열을 오름차순으로 정렬 후 세 개의 포인터를 이용히여 합이 0인지 비교해 나갑니다.

  1. 입력받은 배열을 복사하고 오름차순으로 정렬한다.
  2. 인덱스 i 부터 nums.length - 2 까지 반복한다. (세 개의 숫자가 필요하므로 nums의 자료 끝까지 반복할 필요가 없습니다.)
  3. 인덱스 j = i + 1, k = nums.length - 1 로 설정한다.

  4. 세 개의 값 모두 더한 값이 0 보다 작으면 인덱스 j 를 1 증가 시킨다.

    1. 그 이유는 0 보다 작다는 것은 값이 너무 작다는 의미이므로 오름차순으로 정렬 되어있으므로 index를 1을 증가시켜 수를 크게 만듭니다.

  5. 세 개의 값 모두 더한 값이 0 보다 크면 인덱스 k 를 1 감소 시킨다.

    1. 그 이유는 0 보다 크다는 것은 값이 너무 크다는 의미이므로 오름차순으로 정렬 되어있으므로 index를 1을 감소시켜 수를 작게 만듭니다.
  6. 숫자 값이 중복될 수 있으므로 숫자 값이 같을 경우 j++, k— 시킨다.
  7. 위 과정을 계속 반복하여 결과를 도출합니다.
function solution(nums) {
  const results = [];

	if (nums.length < 3) {
    return results;
  }

	const orderedNums = nums.slice().sort((a, b) => a - b);

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

		let j = i + 1;
		let k = orderedNums.length - 1;

		while (j < k) {
			let sum = orderedNums[i] + orderedNums[j] + orderedNums[k];

			if (sum === 0) {
				results.push([orderedNums[i], orderedNums[j], orderedNums[k]]);

				while (orderedNums[j] === orderedNums[j + 1]) {
          j++;
        }
				while (orderedNums[k] === orderedNums[k - 1]) {
          k--;
        }

				j++;
				k--;
			} else if (sum < 0) {
				j++;
			} else {
				k--;
			}
		}
	}

	return results;
};