[LeetCode] 3Sum

📄 [LeetCode] 3Sum

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.

 

Notice that the solution set must not contain duplicate triplets.

 

func threeSum(_ nums: [Int]) -> [[Int]] {
    
    let testcase = nums.sorted()
    var result: [Int: Array<Int>] = [:]
    
    // Notice that the solution set must not contain duplicate triplets.
    for index in Int.zero..<nums.count {
        // 정렬 된 값 중에 최소 작은 값이 양수 인 경우에는 값을 구할 수 없으므로 종료합니다.
        if testcase[index] > Int.zero { break }
        
        // 오름차순 된 정렬 값을 기준으로 왼쪽은 음수, 오른쪽에는 양수 인덱스를 구합니다.
        var left = index + 1, right = nums.count - 1
        
        while left < right {
            let sum = testcase[index] + testcase[left] + testcase[right]
            if sum == Int.zero {
                let value = [testcase[index], testcase[left], testcase[right]]
                let hashValue = value.sorted().hashValue
                
                if !result.keys.contains(hashValue) { result[hashValue] = value }
                left += 1
                right -= 1
                continue
            }
            
            if Int.zero > sum { left += 1 }
            else if Int.zero < sum { right -= 1 }
        }
    }
    
    return Array(result.values)
}

---

🚀 REFERENCE

3Sum - LeetCode