๋ฌธ์ ๋งํฌ
3Sum - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
์ ์๋ก ์ด๋ฃจ์ด์ง ๋ฐฐ์ด nums๊ฐ ์ฃผ์ด์ง ๋, nums์ element 3๊ฐ๋ฅผ ๋ฝ์ ๋ ํ ๊ฒฝ์ฐ 0์ด ๋๋ element๋ค์ ์ถ๋ ฅํ๋ ๋ฌธ์ ์ด๋ค.
์ ์ ์์๋ ์ค๋ณต๋์ด ์ฃผ์ด์ง ์ ์๊ณ , ์ค๋ณต๋์ด ์ฌ์ฉํ ์ ์๋ค.
์ ๊ทผ ๋ฐฉ๋ฒ
์ฒ์์๋ start, mid, end 3๊ฐ์ ๋ณ์๋ฅผ ํตํด nums๋ฅผ ์ํํ๋ฉฐ 0์ด ๋๋ ๊ฒฝ์ฐ๋ฅผ ์ถ๋ ฅํ๋ ค ํ์๋ค.
ํ์ง๋ง [0,0,0,0] => [0,0,0] ์ด ์ถ๋ ฅ๋์ด์ผ ํ๋๋ฐ [[0,0,0],[0,0,0]] ์ฒ๋ผ ์ค๋ณต๋๋ ๊ฒฝ์ฐ๋ฅผ ์ก์ง ๋ชปํ์ฌ์ ๋ง์ ์๋ฌ๊ฐ ๋ฐ์ํ์ฌ ์ด๋ ค์์ ๊ฒช์๋ค.
๊ฒฐ๊ตญ ๊ฒ์์ ํตํด ์์ธ ์กฐ๊ฑด์ ํ์ธํ์๋๋ฐ
while๋ฌธ ๋ด์ while์ ์ฌ์ฉํ์ฌ ์ด์ ๊ฐ๊ณผ ๋ค์ ๊ฐ์ด ๊ฐ์๋ ๊ณ์ํด์ ์ฆ๊ฐํด์ฃผ๋ ๊ฒ์ผ๋ก ํด๊ฒฐํ์๊ณwhile(start < end && nums[start] === nums[start + 1]) start++;โ
๊ธฐ์กด์ start, mid, end 3๊ฐ์ง๋ฅผ ์์ธ์ฒ๋ฆฌ ํ๋ ๊ฒ์์
start๋ฅผ ๊ณ ์ ๊ฐ์ผ๋ก ๋๊ณ , mid, end๋ฅผ ๋ณํํ๋ ๊ฐ์ผ๋ก ๋๋ ์ธ์ฌ์ดํธ๋ฅผ ์ป์ด ๋ ๊น๋ํ ์ฝ๋๋ฅผ ์งค ์ ์์๋ค.
[Leetcode / Javascript] 15. 3Sum (tistory.com)
// ์ซ์ ๋ฐฐ์ด์ด ์ฃผ์ด์ง๋ 3๊ฐ๋ฅผ ๋ฝ์ ๋ํ์ ๊ฒฝ์ฐ 0์ด ๋๋ ๊ฒฝ์ฐ
// ๊ทธ ์ซ์๋ค์ ๋ฐฐ์ด๋ก ๋ฃ์ด ์ถ๋ ฅ
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
let output = [];
let fixed = 0, start = 1, end = nums.length-1;
if(nums.length < 3) return output;
nums.sort((a, b) => a - b);
for(let fixed = 0; fixed < nums.length - 2; fixed++){
if(nums[fixed] > 0) break;
if(nums[fixed] === nums[fixed - 1]) continue;
let start = fixed + 1, end = nums.length-1;
while(start < end){
const sum3Nums = nums[fixed] + nums[start] + nums[end];
if(sum3Nums === 0) {
output.push([nums[fixed], nums[start], nums[end]])
while(start < end && nums[start] === nums[start + 1]) start++;
while(start < end && nums[end] === nums[end-1]) end--;
start++, end--;
continue;
}
else if(sum3Nums < 0){
while(start < end && nums[start] === nums[start + 1]) start++;
start++;
}else{
while(start < end && nums[end] === nums[end-1]) end--;
end--;
}
}
}
return output
};
'์ฝ๋ฉํ ์คํธ > LeetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[LeetCode] Valid Parentheses (0) | 2022.06.24 |
---|---|
[LeetCode] 3Sum Closest (0) | 2022.06.23 |
[LeetCode] Furthest Building You Can Reach (0) | 2022.06.21 |
[LeetCode] search-suggestions-system (0) | 2022.06.19 |
[LeetCode] Zigzag Conversion (0) | 2022.06.17 |