[LeetCode] 15. 3Sum

https://leetcode.com/

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.

Example 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.

 

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

 

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

 

Code :

var threeSum = function(nums) {
    let result = [];
    // 배열을 오름차순으로 정렬
    let sortedNums = nums.sort((a, b) => a - b);
    // 첫 번째 숫자를 기준으로 순회
    for (let i = 0; i < sortedNums.length - 2; i++) {
        // 중복된 숫자는 건너뛰기
        if (i !== 0 && sortedNums[i] === sortedNums[i - 1]) {
            continue;
        }
        let num1 = sortedNums[i];
        // 나머지 두 숫자의 합을 찾을 때 사용할 맵
        let map = new Map();
        let target1 = num1 * (-1);
        // 두 번째 숫자를 기준으로 순회
        for (let j = i + 1; j < sortedNums.length; j++) {
            let num2 = sortedNums[j];
            // 세 번째 숫자를 찾기 위해 필요한 값
            let k = map.get(target1 - num2);
            // 중복된 숫자는 건너뛰기
            if (sortedNums[j] === sortedNums[j + 1]) {
                map.set(num2, j);
                continue;
            }
            // 조합을 찾으면 결과 배열에 추가
            if ((k !== undefined) && (i !== j) && (j !== k) && (k !== i)) {
                result.push([num1, num2, sortedNums[k]]);
            }
            // 맵에 현재 숫자와 인덱스 저장
            map.set(num2, j);
        }
    }
    return result;
};

 

Solutions Code :

// Solutions Code 1
function threeSum(nums) {
	const results = []
	// 우리가 적어도 3개의 숫자를 가지고 논의할 필요가 없는 경우는 분명히 무의미합니다!
	if (nums.length < 3) return results
	// 숫자를 오름차순으로 정렬하는 것은 이 문제를 훨씬 쉽게 만들어줍니다.
	// 또한, 전체 문제를 해결하는 데 O(N^2) 시간이 걸릴 것이라는 사실을 알고 있기 때문에,
	// O(NlogN) 정렬 작업을 수행할 수 있습니다.
	nums.sort((a, b) => a - b)
    // 질문에서 특정 타겟을 요구한다면, 여기서 타겟을 제어할 수 있습니다.
	let target = 0
	for (let i = 0; i < nums.length - 2; i++) {
		// `i`는 정렬된 세트에서 "왼쪽"에 있는 숫자를 나타냅니다.
		// 이 숫자가 0보다 크면, 양수가 음수에 합산될 수 없으므로 더 이상 진행할 필요가 없습니다.
		if (nums[i] > target) break
		// 반복을 원하지 않으므로 이미 본 숫자를 건너뜁니다.
		if (i > 0 && nums[i] === nums[i - 1]) continue
		// `j`는 `i`와 `k` 사이의 "중간" 요소를 나타냅니다.
		// 우리는 이것을 배열을 통해 증가시킬 것이며, `i`와 `k`는 그들의 위치에 고정됩니다.
		// 우리는 배열을 통해 `k`를 감소시킬 것이고, 마지막으로 `j`와 `k`가 만나면 `i`를 증가시킬 것입니다.
		let j = i + 1
		// `k`는 "오른쪽" 가장 요소를 나타냅니다.
		let k = nums.length - 1
		// 우리의 설정을 요약하면, 우리는 `i`가 시작하는 것을 가지고 있고,
		// `k`가 끝에서 시작하고, `j`가 두 개 사이에서 경주하는 것입니다.
		// `i`는 외부 for 루프에 의해 제어되고 가장 느리게 움직일 것입니다.
		// 그동안 `j`와 `k`는 우리가 아래에 설정할 어떤 로직에 따라 서로에게 다가갈 차례를 갖게 될 것입니다.
		// 그들이 충돌하면 `i`가 증가될 것이고 우리는 프로세스를 반복할 것입니다.
		while (j < k) {
			let sum = nums[i] + nums[j] + nums[k]
			// 우리가 목표 합계를 찾으면 `j`를 증가시키고 `i`가 앵커인 다른 잠재적인 조합을 위해 `k`를 감소시킵니다.
			if (sum === target) {
				// 유효한 세 숫자의 합을 저장합니다.
				results.push([nums[i], nums[j], nums[k]])

				// 이것은 중요합니다! 우리는 `j`를 계속 증가시키고 `k`를 계속 감소시켜야 합니다.
				// 그 값이 중복되는 한 계속해야 합니다. 즉, 이미 본 값을 건너뛰고 싶습니다.
				// 그렇지 않으면 [-2,0,0,2,2] 입력 배열은 [[-2,0,2], [-2,0,2]]로 결과가 나올 것입니다.
				// (이 부분은 while 루프를 하나 더 수행하고 있기 때문에 별로 좋아하지 않습니다...)
				while (nums[j] === nums[j + 1]) j++
				while (nums[k] === nums[k - 1]) k--

				// 마지막으로, 우리는 실제로 `j`를 앞으로 이동하고 `k`를 뒤로 이동시켜야 합니다.
				// 이전 while 루프에서는 이를 처리하지 않습니다.
				j++
				k--
			// 합계가 너무 작으면, `j`를 증가시켜 타겟에 더 가까이하십시오.
			} else if (sum < target) {
				j++
			// 합계가 너무 크면, `k`를 감소시켜 타겟에 더 가까이하십시오.
			} else { // (sum > target)
				k--
			}
		}
	}
	return results;
};

// Solution Code 2
var threeSum = function(nums) {
    const res = []; // 결과를 담을 배열
    nums.sort((a, b) => a - b); // 숫자를 정렬

    // 주어진 조건에 따라 세 수의 합이 0이 되는 모든 유일한 조합을 찾습니다.
    for (let i = 0; i < nums.length - 2; i++) {
        if (i === 0 || nums[i] !== nums[i-1]) { // 중복된 값을 제거
            let lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i]; // lo, hi를 설정하고 합을 계산합니다.
            while (lo < hi) { // lo가 hi보다 작은 동안 반복합니다.
                if (nums[lo] + nums[hi] === sum) { // 세 수의 합이 0이 되는 경우
                    res.push([nums[i], nums[lo], nums[hi]]); // 결과에 해당 조합을 추가합니다.
                    while (lo < hi && nums[lo] === nums[lo+1]) lo++; // 중복된 값을 제거합니다.
                    while (lo < hi && nums[hi] === nums[hi-1]) hi--; // 중복된 값을 제거합니다.
                    lo++; // lo 증가
                    hi--; // hi 감소
                } else if (nums[lo] + nums[hi] < sum) { // 합이 sum보다 작은 경우
                    lo++; // lo 증가
                } else { // 합이 sum보다 큰 경우
                    hi--; // hi 감소
                }
            }
        }
    }
    
    return res; // 결과 반환
};

 

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

Problems - LeetCode