[LeetCode] 15. 3Sum - Java

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

3Sum - LeetCode

---

문제

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 duplicate triplets.

 

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

 

Constraints:

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

---

풀이

풀이 과정

입력받은 nums 배열의 값들 중에서 세 개를 골라 더했을 때 0이되는 값들을 구하는 문제이다. 이 때 중복된 값은 제외한다.

우선 문제의 조건인 더해서 0이 되기 위해서는 배열이 모두 양수이거나 모두 음수인 경우는 0을 만드는 것이 불가능하다.
이 조건을 먼저 판단하기 위해 배열을 정렬한다.
정렬된 배열의 첫 번째 값이 양수이면 모두 양수로 이루어진 배열이므로 0을 만드는 것이 불가능하고
마지막 값이 음수이면 모두 음수로 이루어진 배열이므로 역시 0을 만드는 것이 불가능하다.

// 정답 리스트
List<List<Integer>> answer = new ArrayList<>();

// nums 배열을 정렬
// 배열의 첫 번째 값이 양수인 경우 ( 양수로만 이루어진 경우 )
// 배열의 마지막 값이 음수인 경우 ( 음수로만 이루어진 경우 )
// 0이 될수 없으므로 빈 리스트를 return
Arrays.sort(nums);
if(nums[0] > 0 || nums[nums.length - 1] < 0) return answer;

 

다음으로 정렬된 배열을 가지고 투 포인터를 사용한다.
i번째 인덱스를 기준으로 다음 인덱스를 left 포인터로, 마지막 인덱스를 right 포인터로 정의한다.

// i번째 값을 기준으로 다음 인덱스를 left, 마지막 인덱스를 right로 정의
for(int i = 0; i < nums.length - 2; i++) {
    int left = i + 1;               // 왼쪽 포인터
    int right = nums.length - 1;    // 오른쪽 포인터
}

중복된 탐색을 피하기 위해서 탐색 중 i번째 값이 이전 값과 같다면 탐색을 건너뛴다.

// i번째 값이 이전값과 같다면 탐색에서 제외
if(i > 0 && nums[i] == nums[i - 1]) continue;

이제 left와 right가 서로 겹칠 때 까지 반복하며 nums[i], nums[left], nums[right]의 합을 구한다.
만약 세 수의 합이 0이 된다면 정답리스트에 추가하고 left와 right를 각각 새로운 값이 나올 때 까지 이동한다.

// nums[i], nums[left], nums[right]의 합이 0이 된다면 정답리스트에 추가하고
// 다른 값이 나올 때까지 각 포인터 이동
if(sum == 0) {
    answer.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--;
}

세 수의 합이 0보다 크다면 값을 감소시켜야 하므로 right 인덱스를 새로운 값이 나올 때까지 감소시키고,
0보다 작다면 값을 증가시켜야 하므로 left 새로운 값이 나올 때까지 인덱스를 증가시킨다

// 합이 0보다 크다면 다른값이 나올 때까지 right 인덱스 감소
if(sum > 0) {
    right --;
    while(left < right && nums[right] == nums[right + 1]) right--;
}
// 합이 0보다 작다면 다른값이 나올 때까지 left 인덱스 증가
if(sum < 0) {
    left++;
    while(left < right && nums[left] == nums[left - 1]) left++;
}

---

최종 코드

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 정답 리스트
        List<List<Integer>> answer = new ArrayList<>();

        // nums 배열을 정렬
        // 배열의 첫 번째 값이 양수인 경우 ( 양수로만 이루어진 경우 )
        // 배열의 마지막 값이 음수인 경우 ( 음수로만 이루어진 경우 )
        // 0이 될수 없으므로 빈 리스트를 return
        Arrays.sort(nums);
        if(nums[0] > 0 || nums[nums.length - 1] < 0) return answer;
        
        
        // i번째 값을 기준으로 다음 인덱스를 left, 마지막 인덱스를 right로 정의
        for(int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;               // 왼쪽 포인터
            int right = nums.length - 1;    // 오른쪽 포인터
            
            // i번째 값이 이전값과 같다면 탐색에서 제외
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            
            // left와 right가 겹칠때 까지 탐색
            while(left < right) {
                // 세 인덱스 값의 합
                int sum = nums[i] + nums[left] + nums[right];
                
                // i, left, right의 합이 0이 된다면 정답리스트에 추가하고
                // 다른 값이 나올 때까지 각 포인터 이동
                if(sum == 0) {
                    answer.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--;
                }
                // 합이 0보다 크다면 다른값이 나올 때까지 right 인덱스 감소
                if(sum > 0) {
                    right --;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
                // 합이 0보다 작다면 다른값이 나올 때까지 left 인덱스 증가
                if(sum < 0) {
                    left++;
                    while(left < right && nums[left] == nums[left - 1]) left++;
                }
            }
        }

        return answer;
    }
}

---