15. 3Sum

문제 링크

https://leetcode.com/problems/3sum/description/

 

해결 1.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n= nums.length;
        List<List<Integer>> answer=new ArrayList<>();
        //중복을 방지하고자 임시로 사용할 Set을 선언하였다.
        Set<List<Integer>> temp=new HashSet<>();
         // 배열을 먼저 정렬하여 중복 및 순서 문제를 해결
        Arrays.sort(nums);
        for(int i=0;i<n;i++) {
            int target = 0-nums[i];
            // 공간복잡도: O(n)
            // 입력 배열의 길이와 비례해서 증가
            Set<Integer> set = new HashSet<>();
            for(int j=i+1;j<n;j++) {
                int composition = target-nums[j];
                if(set.contains(composition)) {
                    List<Integer> triplet = Arrays.asList(nums[i], nums[j], composition);
                    // 서로 다른 배열에 동일한 요소들이 포함되어 있어도 요소의 순서가 다르면 서로 다른 값으로 
                    // 처리하기 때문에 배열을 정렬 후 Set에 추가하였다.
                    Collections.sort(triplet);
                    temp.add(triplet);
                }
                    
                
                set.add(nums[j]);
            }
        }
        //Set의 값들을 List에 추가
        answer.addAll(temp);
        return answer;
    }
}

- 시간 복잡도: O(n^2)

- 공간 복잡도: O(n)

 

해결 2.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> answer = new ArrayList<>();
        int n=nums.length;
        Arrays.sort(nums);
        for(int i=0;i<n-2;i++) {
            int left=i+1;
            int right=n-1;

            //중복 처리를 방지
            if(i>0 && nums[i]==nums[i-1])
                continue;

            while(left<right) {
                

                int sum = nums[i]+nums[left]+nums[right];
                if(sum==0) {
                    answer.add(List.of(nums[i], nums[left], nums[right]));

                    //중복 처리를 방지
                    while(left<right && nums[left]==nums[left+1]) {
                        left++;
                    }
                        
                    //중복 처리를 방지
                    while(left>right && nums[right]==nums[right-1]) {
                        right--;
                    }

                    left+=1;
                    right-=1;
                }
                else if(sum<0) {
                    left+=1;
                }
                else {
                    right-=1;
                }
            }
        }
        return answer;
    }
}

- 시간 복잡도: O(n^2)

- 공간 복잡도: O(1)