3Sum

문제

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

입력

3 <= nums.length <= 3,000 // Int 배열 
-10^5 <= nums[i] <= 10^5

결과

ans: [[Int]] = 중복되지 않은 3개 숫자의 합이 0이되는 조합 배열 
ex) [[-1,-1,2],[-1,0,1]]

해석

2포인터 개념에 하나의 트릭을 숨겨논 문제로 해석된다.

3개의 합이 0이되는 지 검사해야하는데 2포인터로 접근하려면 어떻게야할까 ??

 

간단하게 한개를 고정하고 나머지 2개만 움직이면 된다.

 

배열의 길이가 최대 3000이므로 정렬을 통해 조금 더 쉽게 포인터를 움직일 수 있는 전처리를 수행한 후 

중복이 허용되지 않으므로 같은 값이 있을 경우 과감히 다음 값으로 넘어간다.

 

여기서 내가 고정할 값은 i 이며 , j를 바로 i 다음, j를 오른쪽 끝에서 시작해서 조건에 맞게 움직이자.

코드

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        let n = nums.count
        let nums = nums.sorted()
        var ans: [[Int]] = []

        for i in 0..<n {
            if i > 0 && nums[i] == nums[i-1] { // 중복값 건너뜀
                continue 
            }

            var j = i+1 
            var k = n-1

            while j < k {
                let acc = nums[i] + nums[j] + nums[k]

                if acc > 0 { // 오른쪽 포인터 이동
                    k -= 1 
                } else if acc < 0 { // 왼쪽 포인터 이동
                    j += 1 
                } else {
                    ans.append([nums[i], nums[j], nums[k]])
                    j += 1

                    while j < k && nums[j] == nums[j-1] { // 중복된 값 건너뜀
                        j += 1 
                    } 
                }
            }
        } 
        
        return ans
    }
}