3Sum

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

3Sum - LeetCode

 

배열의 3 요소를 합쳤을 때 값이 0이 되는 조합을 찾는 문제이다. 이 때 같은 숫자의 조합은 중복되어 처리하지 않는다.

 

우선 처리한 일은 배열의 정렬이다. 인덱스를 순화하며 값의 변화를 예측하기 위해 정렬해주었다.
정렬이 후에는 조합의 합계를 늘리기 위해선 특정 요소의 인덱스를 올리면 되고 낮추기 위해선 인덱스를 낮추면 된다.

 

요소를 찾기 위해서는 결국 각 인덱스를 순환해야 한다. 이 때 첫 인덱스를 고정적으로 증가시키며 지정해두고, 합계의 값을 비교하여 두 인덱스를 조절하며 조합을 찾아내었다. 중복 요소를 제거하기 위하여, 인덱스를 조절할 때 이전과 같은 경우 인덱스를 추가로 증감하여 같은 값을 제외시켰다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> threeSum(int[] nums) {  
        int n = nums.length;  
  
        List<List<Integer>> answer = new ArrayList<>();  
        Arrays.sort(nums);  
  
        for(int i = 0; i < n - 2; i++){  
            if(i > 0 && nums[i - 1] == nums[i]) continue;  
  
            int j = i + 1;  
            int k = n - 1;  
            while(j < k){  
                int num1 = nums[i];  
                int num2 = nums[j];  
                int num3 = nums[k];  
                if(num1 + num2 + num3 == 0){  
                    List<Integer> triple = new ArrayList<>();  
                    triple.add(num1);  
                    triple.add(num2);  
                    triple.add(num3);  
                    answer.add(triple);  
                }  
  
                if(num1 + num2 + num3 <= 0){  
                    j++;  
                    while(nums[j] == nums[j - 1] && j < k){  
                        j++;  
                    }  
                }else if(num1 + num2 + num3 > 0){  
                    k--;  
                    while(nums[k] == nums[k + 1] && j < k){  
                        k--;  
                    }  
                }  
            }  
        }  
  
  
        return answer;  
    }