3주차. 배열(세수의 합)

09. 세수의 합

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

3Sum - LeetCode

📌문제
배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라

  
- 예제1
  📝입력

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

  💻출력

[[-1,-1,2],[-1,0,1]]

  
 - 예제2

  📝입력
 

nums = [0,1,1]

  💻출력
 

[]

    
📌풀이
1. 투포인터로 합 계산(23ms, 46.7mb)

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    // 중복제거 contain 함수 사용시 시간초과가 걸림
    List<List<Integer>> list = new ArrayList<>();
    for(int i = 0; i < nums.length-2; i++){
        if(nums[i] > 0) continue;
        int left = i+1, right = nums.length - 1;
        while(left<right){
            int sum = nums[i] + nums[left] + nums[right];
            if(sum > 0) right--;
            else if(sum < 0) left++;
            else{
                list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                right--;
                // 시간초 줄이기위한 예외처리
                // 같은 수를 굳이 다시 검사할 필요가 없으니 ++
                while((left < right) && (nums[left] == nums[left-1]))left++;
                while((left < right) && (nums[right] == nums[right+1]))right--;
            }
        }
        // 시간초 줄이기위한 예외처리
        // 같은 수를 굳이 다시 검사할 필요가 없으니 ++
        while(nums[i] == nums[i+1] && i < nums.length - 2) i++;
    }
    return new ArrayList<>(list);
}