3Sum

LeetCode 15: 3Sum

원문

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.

풀이

1. nums를 오름차순으로 정렬한다.
   
2. nums를 순회한다.
   1. 인덱스 i가 0보다 클 때 nums[i]가 nums[i - 1]과 같다면 넘어간다.
   2. i + 1을 lo, nums의 길이에서 1을 뺀 것을 hi라고 하자.
   3. lo가 hi보다 크거나 같게 되기 전까지 다음을 반복한다.
      1. nums[i] + nums[lo] + nums[hi]의 값을 구한다.
      2. 구한 값이 0이면
         1. 결과 배열에 [i, lo, hi]를 추가하고, lo에 1을 더한다.
         2. 만약 nums[lo]와 nums[lo - 1]이 같다면 달라질 때까지 lo에 1을 더한다.
      3. 구한 값이 0보다 작다면 lo에 1을 더한다.
      4. 구한 값이 0보다 크다면 hi에서 1을 뺀다.
3. 결과 배열을 반환한다.

코드

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = list()

        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]: continue
            lo, hi = i + 1, len(nums) - 1
            while lo < hi:
                if (nums[lo] + nums[hi]) == -nums[i]:
                    result.append([nums[i], nums[lo], nums[hi]])
                    lo += 1

                    while nums[lo] == nums[lo - 1] and lo < hi:
                        lo += 1

                elif (nums[lo] + nums[hi]) < -nums[i]: lo += 1
                else: hi -= 1
        
        return result

Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int lo = i + 1;
            int hi = nums.length - 1;

            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum == 0) {
                    result.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[lo], nums[hi])));
                    lo++;
                    while (nums[lo] == nums[lo - 1] && lo < hi) {
                        lo++;
                    }
                } else if (sum < 0) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }

        return result;
    }
}