LeetCode - 15. 3Sum

3Sum - LeetCode

---

문제

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.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

 

---

3개 합쳐서 0이 되는 모든 경우를 찾는 문제이다.

a + b + c = 0 이면 b + c = -a 와 같다.

그냥 iterate하면 시간이 너무 오래 걸린다.

기존 배열을 정렬해서 high low 포인터를 통해 sum 이 되는 경우를 찾는다.

중복되면 무시하기 때문에 HashSet<List> 를 사용한다.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        List<List<Integer>> answer = new ArrayList<>();
        Arrays.sort(nums);
        HashSet<List<Integer>> set = new HashSet<>();
        System.out.println(Arrays.toString(nums));
        for(int i = 0 ; i < len ; i++){
            if(i==0 || (i > 0 && nums[i] != nums[i-1])){
                int low = i+1;
                int high = nums.length-1;
                int sum = 0-nums[i];
                while(low < high){
                    if(nums[low] + nums[high] == sum){
                        answer.add(Arrays.asList(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(nums[low] + nums[high] > sum){
                        high--;
                    }else{
                        low++;
                    }
                    System.out.println("sum : "+ sum + " / " + nums[i] + " "  + nums[low] + " " + nums[high]);
                }
            }
            
        }
        return answer;
        
    }
}