0015 3Sum

Solved at: 2023-01-30 3Sum - LeetCode

Question

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.

Solution

swift

class Solution {    func threeSum(_ numsOriginal: [Int]) -> [[Int]] {        var map = [Int: [(Int, Int)]]()
        var counter = [Int: Int]()
        for (i, x) in numsOriginal.enumerated() {            if counter.keys.contains(x) {                counter[x] = min(3, counter[x]! + 1)            } else {                counter[x] = 1            }        }
        var nums : [Int] = []
        for (i, (key, val)) in counter.enumerated() {            for i in 0..<val {                nums.append(key)            }        }
        for (i, x) in nums.enumerated() {            for j in (i+1) ..< nums.count {                if !map.keys.contains(nums[i] + nums[j]) {                    map[nums[i] + nums[j]] = [(i, j)]                } else {                    map[nums[i] + nums[j]]!.append((i, j))                }            }        }
        var set = Set<[Int]>()
        for (i, val) in nums.enumerated() {            if map.keys.contains(0 - val) {                let candidates = map[0 - val]!                for candidate in candidates {                    let (first, second) = candidate                    if first != i && second != i {                        var ans = [nums[first], nums[second], nums[i]]                        ans.sort {$0 < $1}                        set.insert(ans)                    }                }            }        }        return Array(set)    }}

class Solution {    func threeSum(_ numsOriginal: [Int]) -> [[Int]] {        var map = [Int: [(Int, Int)]]()
        var counter = [Int: Int]()
        for (i, x) in numsOriginal.enumerated() {            if counter.keys.contains(x) {                counter[x] = min(3, counter[x]! + 1)            } else {                counter[x] = 1            }        }
        var nums : [Int] = []
        for (i, (key, val)) in counter.enumerated() {            for i in 0..<val {                nums.append(key)            }        }
        for (i, x) in nums.enumerated() {            for j in (i+1) ..< nums.count {                if !map.keys.contains(nums[i] + nums[j]) {                    map[nums[i] + nums[j]] = [(i, j)]                } else {                    map[nums[i] + nums[j]]!.append((i, j))                }            }        }
        var set = Set<[Int]>()
        for (i, val) in nums.enumerated() {            if map.keys.contains(0 - val) {                let candidates = map[0 - val]!                for candidate in candidates {                    let (first, second) = candidate                    if first != i && second != i {                        var ans = [nums[first], nums[second], nums[i]]                        ans.sort {$0 < $1}                        set.insert(ans)                    }                }            }        }        return Array(set)    }}

Results

Time taken: 30 m 39 s
Runtime 2424 ms, Beats 10.20%
Memory 156.2 MB, Beats 6.9%

Complexity Analysis

$O(N^2)$ for both, worst case. $O(N^2)$ for both, worst case.