Leetcode - 3Sum
Description
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0. Find all unique triplets in the array which gives the sum of zero.
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]]
Example 2
Input
nums = []
Output
[]
Example 3
Input
nums = [0]
Output
[]
Approach
Brute force might be a solution to get the three sums which equal zero. However, brute force is not an efficient algorithm as size of array increases O(N^2). Hence, two pointer algorithm is implemented here to ensure O(N) time complexity.
Solutions
Solution I (Python)
class Solution(object):
def threeSum(self, nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
left = i + 1
right = len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left = left + 1
elif total > 0:
right = right - 1
else:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left = left + 1
while left < right and nums[right] == nums[right-1]:
right = right - 1
left = left + 1
right = right - 1
return result
Result
Runtime: 664 ms
Memory Usage: 16 MB
Runtime Beats 70.73% of Python Submission
Solution II (JavaScript)
var threeSum = function(nums) {
nums = nums.sort((a, b) => a - b);
let result = [];
let target = 0
let low, high, sum;
if(nums.length < 3) return result;
for(let i = 0; i < nums.length - 2; i++) {
if(i > 0 && nums[i] === nums[i-1]) continue;
low = i + 1;
high = nums.length - 1;
while(low < high) {
sum = nums[i] + nums[low] + nums[high];
if(sum === target) {
result.push([nums[i], nums[low], nums[high]]);
while(low < high && nums[low] === nums[low + 1]) low++;
while(low < high && nums[high] === nums[high - 1]) high--;
low++;
high--;
} else if(sum < target) {
low++;
} else {
high--;
}
}
}
return result;
};
Result
Runtime: 160 ms
Memory Usage: 46.9 MB
Runtime Beats 55.27% of JavaScript Submission
Author And Source
이 문제에 관하여(Leetcode - 3Sum), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jiselectric/Leetcode-3Sum저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)