LeetCode – 18. 4Sum

題目連結: https://leetcode.com/problems/4sum/

法ㄧ: (Time complexity: O(n^4))

    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        let sort = nums.sorted()
        var result: [[Int]] = []
        for i in 0 ..< (nums.count - 3){
            for j in (i+1) ..< (nums.count - 2) {
                for k in (j+1) ..< (nums.count - 1) {
                    for l in (k+1) ..< nums.count {
                        if target == sort[i] + sort[j] + sort[k] + sort[l] {
                            result.append([sort[i], sort[j], sort[k], sort[l]])
                        }
                    }
                }
            }
        }
        return result
    }

法二: Time complexity: O(n^3)

func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
    guard nums.count >= 4 else { return [] }
    let sort = nums.sorted()
    var resultSet: Set<[Int]> = []
    for i in 0 ..< (sort.count - 3) {
        for j in (i+1) ..< (sort.count - 2) {
            let sum = target - (sort[i] + sort[j])
            var left = j + 1
            var right = sort.count - 1
            while left < right {
                if sum == (sort[left] + sort[right]) {
                    resultSet.insert([sort[i], sort[j], sort[left], sort[right]])
                    left += 1
                    right -= 1
                } else if sum > (sort[left] + sort[right]) {
                    left += 1
                } else {
                    right -= 1
                }
            }
        }
    }
    return resultSet.map { $0 }
}