[LeetCode] 15. 3Sum / Swift

[문제 보기]

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]]

Example 2:

Input: nums = [] Output: []

Example 3:

Input: nums = [0] Output: []

 

Constraints:

• 0 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

 

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

3Sum - LeetCode

 

---

분명 2sum 문제는 풀었던 기억이 있었는데 2sum문제에서 푼 방법(brute force)는 역시 3이 되니 시간초과가 났다!

이번 문제도 역시 투포인터 문제였다.

k - 1까지는 한개씩 후보를 줄여나가면서 직접 찾고, 나머지 2개를 찾을 때는 투포인터를 사용한다.

여기서 중복되지 않는 부분을 잘 끼워넣는게 이해하기가 많이 어려웠다.

중복되는 것을 피하기 위해 set도 사용해보았지만 (1,1,0) 같은 경우가 있어서 생각해보다가 결국은 discuss에 있는 방법을 보았다.

 

if i > 0 && arr[i] == arr[i - 1] { continue } // 정렬했으므로 중복 제거할수있다

위 코드는 가장 먼저 나오는 중복제거 부분이다.

한번 정렬하고서 순회하면서 후보를 찾아나가는데, 연속해서 같은 값이 들어올 경우 결과값도 동일하므로 제외해야한다.

예) [1,1,2,2,4,4,4] 인 경우

가장 맨 앞의 1에 대해서 경우를 찾아두었다면, 두번째 1도 첫번째 1과 마찬가지로 같은 결과의 쌍들을 갖게 된다.

 

while left < right && arr[left] == arr[left + 1] { left += 1 } // 중복되는 원소가 안나올때까지 이동
while left < right && arr[right] == arr[right - 1] { right -= 1 } // 중복되는 원소가 안나올때까지 이동
left += 1; right -= 1

위 코드는 두번째로 나오는 중복제거 부분이다.

이 코드는 투포인터 영역에 있는데, 한번 답을 찾았다면 그 다음 left와 right의 각각의 원소가 현재 원소 값과 같다면 결과도 같게 되므로 중복이 발생한다. 이 경우를 피하기 위해 동일한게 나오지 않을 때까지 이동시킨다.

예) [1,1,2,2,3,3,3], target = 4 인 경우

가장 맨 앞의 1과 가장 끝의 3을 가장 먼저 답으로 찾게 된다. 그런데 left의 그 다음도 1이고, right의 앞쪽도 3이라서 중복된 결과를 가져온다. 결과를 저장하는 부분을 ans.append()로 그냥 넣어주고 싶기 때문에 미리 겹치지 않게 잘 넣어야한다.

left는 가장 마지막 중복되는 1 (두번째 1)로 밀어주고, right도 가장 마지막(가장처음으로 나오는)으로 나오는 3으로 밀어주어야 중복없이 넣을 수 있게 된다. 

그리고 계속해서 다음번째의 정답을 탐색하기 위해(투포인터) left와 right 모두 각각 이동하는 것도 잊지말자.(left: 1->2), (right: 3->2)

 

// 제출 코드
class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        if nums.count < 3 { return [] }
        var ans = [[Int]]()
        var arr = nums.sorted()
        for i in (0..<arr.count) {
            if i > 0 && arr[i] == arr[i - 1] { continue } // 정렬했으므로 중복 제거할수있다
            var left = i+1, right = arr.count - 1
            let remain = 0 - arr[i]
            while left < right {
                let sum = arr[left] + arr[right]
                if sum == remain {
                    ans.append([arr[i], arr[left], arr[right]])
                    while left < right && arr[left] == arr[left + 1] { left += 1 } // 중복되는 원소가 안나올때까지 이동
                    while left < right && arr[right] == arr[right - 1] { right -= 1 } // 중복되는 원소가 안나올때까지 이동
                    left += 1; right -= 1
                } else if sum < remain {
                    left += 1
                } else {
                    right -= 1
                }
            }
        }
        
        return ans
    }
}