[array] 3sum

✅ Problem

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

 

✅ Approach & Solution

방식) 정렬 후 투 포인터 사용

• 3개를 찾아야 할 때 : 1개는 고정해두고 나머지 2개를 찾자
• 나머지 2개 찾을 때 투 포인터 사용
  • 정렬 필수 (배열의 인덱스 값 활용하지 않기 때문에 정렬 가능)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int left, right, sum;
        List<List<Integer>> results = new ArrayList<>();

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            // 중복된 값 건너뛰기 (이전 주체와 동일할 경우 결과도 동일하기 때문에 skip)
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }

            left = i + 1;
            right = nums.length - 1;
            while (left < right) {
                sum = nums[i] + nums[left] + nums[right];

                if (sum < 0) {
                    left += 1;
                } else if (sum > 0) {
                    right -= 1;
                } else { // sum == 0 정답
                    results.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 포인터 조정
                    // 배열이 정렬되어 있어 그 다음에도 동일한 값이 나올 수 있음 (중복되지 않게 건너뛰어야 함)
                    while (left < right && nums[left] == nums[left + 1]) {
                        left += 1;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right -= 1;
                    }

                    left += 1;
                    right -= 1;
                }
            }
        }

        return results;
    }
}