[파이썬 PYTHON · 자바 JAVA] LeetCode【3Sum】

3Sum - LeetCode

---

자바 코드

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로 잡고 3개의 원소의 합이 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 자료구조 특성 상 중복으로 추가되지 않는다.