O(n^3) swift solution


  • 0
    C

    class Solution {

    func fourSum(nums: [Int], _ target: Int) -> [[Int]] {

       if nums.count < 4 { return [] }  // mynums -3 -1 0 2 4 5
        var mynums = nums.sort()
        var result:[[Int]] = []
        for index in 0..<mynums.count-1 {
            if index != 0 && mynums[index] == mynums[index - 1]  {continue}
            for (var j = mynums.count-1; j > index; j -= 1) {
                if j != mynums.count-1 && mynums[j] == mynums[j + 1] {continue}
                var lo = index + 1
                let sum = target - mynums[index] - mynums[j]
                var hi = j-1
                while lo < hi {
                    if sum == mynums[lo] + mynums[hi] {
                        let tempArr: [Int] = [mynums[index], mynums[lo], mynums[hi], mynums[j]]
                        result.append(tempArr)
                        while lo < hi && mynums[lo] == mynums[lo+1] {
                            lo += 1
                        }
                        while lo < hi && mynums[hi] == mynums[hi-1] {
                            hi -= 1
                        }
                        lo += 1
                        hi -= 1
                    } else if (mynums[lo] + mynums[hi] < sum) {
                        lo += 1
                    } else {
                        hi -= 1
                    }
                }
            }
        }
        return result
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.