.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
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]]
Plain Text
복사
Example 2:
Input: nums = []
Output: []
Plain Text
복사
Example 3:
Input: nums = [0]
Output: []
Plain Text
복사
Constraints:
•
0 <= nums.length <= 3000
•
105 <= nums[i] <= 105
My solution
각기 다른 인덱스 세개를 방문해서 그 값을 더했을 때 0이 되는 인덱스를 [index1, index2, index3]으로 반환해라.
two pointer로 해결하기 위해서 하나의 숫자를 선택한 다음 나머지 숫자를 two pointer로 찾아낸다.
따라서 이중 while문을 사용한다.
또한, 입력으로 주어진 값이 증가하는 순서가 아니라서 sort()도 필요하다.(증가하는 방향으로 투포인터 알고리즘을 사용하기 위함)
만약 target을 만드는 세개의 인덱스를 찾아내더라도 추가되어야 할 로직이 있다.
while (i < len - 2) {
let j = i + 1;
let k = len - 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] === 0) {
result.push([nums[i], nums[j], nums[k]]);
j++;
while (j < k && nums[j] === nums[j - 1]) j++; // avoid duplicate
}
JavaScript
복사
가장 먼 위치에서 j, k를 설정했으므로 i를 픽스한 상태로 다른 겹치는 답이 있는지 범위를 좁혀가며 검사하는 것이다. 이를 통해 중복은 제거한다.
j, k를 모두 검사해도 되지만 j만으로도 가능하다.
Code
/**
* @param {number[]} nums
* @return {number[][]}
*/
const threeSum = function (nums) {
let i = 0;
const result = [];
const len = nums.length;
nums.sort((a, b) => a - b);
while (i < len - 2) {
let j = i + 1;
let k = len - 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] === 0) {
result.push([nums[i], nums[j], nums[k]]);
j++;
while (j < k && nums[j] === nums[j - 1]) j++; // avoid duplicate
} else if (nums[i] + nums[j] + nums[k] > 0) {
k--;
} else {
j++;
}
}
i++;
while (i < len - 2 && nums[i] === nums[i - 1]) i++;
}
return result;
};
describe('threeSum', () => {
it('TC1', () => {
expect(threeSum([-1, 0, 1, 2, -1, -4])).toStrictEqual([
[-1, -1, 2],
[-1, 0, 1],
]);
});
it('TC2', () => {
expect(threeSum([])).toStrictEqual([]);
});
it('TC3', () => {
expect(threeSum([0])).toStrictEqual([]);
});
});
JavaScript
복사
