💯 Daily LeetCode Challenge Day_08 - 3Sum

Account Login - LeetCode

---

문제

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

---

저번에 풀었던 문제다.

아이디어가 a+b+c=0 대신 a+b=-c 와 두개의 high low pointer를 사용한게 기억이 난다.

오늘은 Swift로 풀어본다.

---

먼저 brute force

Time Limit Exceed 뜬다. 당연스

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var answer : [[Int]] = []
        var tmp : Set<[Int]> = []
        let len = nums.count
        //a+b+c=0
        //a+b=-c
        for i in 0..<len {
            for j in i+1..<len {
                for k in j+1..<len {
                    if nums[i]+nums[j] == (-1)*nums[k] {
                        var arr = [nums[i],nums[j],nums[k]]
                        tmp.insert(arr.sorted())
                    }
                }
            }
        }
        for i in tmp {
            answer.append(i)
        }
        return answer
    }
}

---

다음 low 와 high pointer를 사용한다.

먼저 주어진 array를 sort 한 뒤 

[-1, 0, 1, 2, -1, -4] -> [-4, -1, -1, 0, 1, 2]

-4를 기준으로 high =  2, low = -1 로 초기값을 정한다.

while(low<high) 동안 high+low 와 -4의 값을 비교해 high+low값이 크면 high를 줄이고, 작으면 low 를 증가시킨다.

몇 가지 추가조건을 통해 일부 경우를 제외시킬 수 있다.

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var answer : [[Int]] = []
        var tmp : Set<[Int]> = []
        let len = nums.count
        //a+b+c=0
        //a+b=-c
        //오름 차순으로 정렬한다.
        var arr = nums.sorted(by: <)
        for i in 0..<len {
            //굳이 없어도 되는 조건이지만 하나의 filter
            if i==0 || i>0 && arr[i] != arr[i-1] {
                //i를 c, low 가 a, high 가 b 역할이다.
                var low = i+1
                var high = len-1
                var sum = 0-arr[i]
                //low 포인터가 high보다 낮을때 루프를 돈다.
                while(low<high){
                    //조건을 만족시킨다면 Set에 추가한다.
                    if arr[low] + arr[high] == sum {
                        tmp.insert([arr[i],arr[low],arr[high]])
                        //굳이 없어도 되는 조건이다. 중복값은 무시하므로 연속된 값이 같다면 pointer를 증가시킨다.
                        while(low<high && arr[low] == arr[low+1]) {low+=1}
                        while(low<high && arr[high] == arr[high-1]) {high-=1}
                        //연속된 값이 아닐때 처리
                        low+=1
                        high-=1
                    }else if (arr[low] + arr[high] > sum){
                        //a+b가 sum보다 큰 상태, high를 내림
                        high -= 1
                    }else{
                        //a+b가 sum보다 작은 상태, low를 올림
                        low += 1
                    }
                }
            }
        }
        //Set to Array
        answer = Array(tmp)
     
        return answer
    }
}