3Sum – LeetCode
Can you solve this real interview question? 3Sum – 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 du
leetcode.com
Java 코드
import java.util.*;
class Solution {
public List<List<Integer>> threeSum(int() nums) {
Arrays.sort(nums);
Set<List<Integer>> set = new HashSet<>();
List<List<Integer>> ans = new ArrayList<>();
for(int i=0;i<nums.length;i++){
int left = i+1;
int right = nums.length-1;
while(left<right){
int sum = nums(i)+nums(left)+nums(right);
if(sum == 0){
set.add(Arrays.asList(nums(i),nums(left),nums(right)));
left+=1;
right-=1;
}else if(sum<0){
left+=1;
}else{
right-=1;
}
}
}
ans.addAll(set);
return ans;
}
}파이썬 코드
class Solution(object):
def threeSum(self, nums):
nums.sort()
_set = set()
for i,num in enumerate(nums):
left = i+1
right = len(nums)-1
while left<right:
_sum = num+nums(left)+nums(right)
if _sum==0:
_set.add((num,nums(left),nums(right)))
left+=1
right-=1
elif _sum<0:
left+=1
else:
right-=1
return list(_set)먼저 nums를 정렬합니다.
그리고, 기준치를 제외한 2개의 포인터 방식을 사용한다.
그리고, 기준치+왼쪽 포인터값+오른쪽 포인터값이 0인 경우는 set에 추가하고, 왼쪽 포인터를 -1, 오른쪽 포인터를 +1해 준다.
0보다 작으면 정렬되어 있으므로 왼쪽 포인터를 1 늘려 확인해 본다.
0보다 큰 경우는 오른쪽 포인터를 1 줄여 확인해 본다.
예를 들어,
(-1, 0, 1, 2, -1, -4) 가 있을 때, 정렬하면 (-4, -1, -1, 0, 1, 2) 가 된다.
그런 다음 기준 -4으로 잡아 세 원소의 합계가 0이 되는 경우의 수를 찾는다.
L R
-4 -1 -1 0 1 2
상기와 같이 좌측 포인터 L이 -1이고 우측 포인터 R이 2인 경우, -4+-1+2=-3이고, 0보다 작다.
합이 0보다 작은 경우에는 L만 증가한다.
이렇게 탐색을 계속한다.
-4가 기준일 때는 3원소의 합계가 0이 되는 경우의 수가 존재하지 않는다.
만약 -1이 기준의 경우
L R
-4 -1 -1 0 1 2
-1 + -1 + 2 = 0이 되므로 set에 추가해 준다.
합이 0이 되는 경우에는 L도 +1해 주고, R도 -1해 준다.
L R
-4 -1 -1 0 1 2
-1+0+1도 합계가 0이므로 set에 추가합니다.
그 후 기준값도 -1인데
L R
-4 -1 -1 0 1 2
상기의 경우는 -1+0+2이므로, 0보다 크다.
따라서 오른쪽 포인터를 줄입니다.
L R
-4 -1 -1 0 1 2
위의 상황이 -1+0+1이므로 합계가 0이고 set에 추가하면 됩니다.
이미 추가되었지만 set 데이터 구조 특성상 중복 추가되지 않습니다.