美文网首页
LeetCode - 15.三数之和 swift

LeetCode - 15.三数之和 swift

作者: huxq_coder | 来源:发表于2020-08-17 10:16 被阅读0次

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

    注意:答案中不可以包含重复的三元组。

    示例:

    给定数组 nums = [-1, 0, 1, 2, -1, -4],

    满足要求的三元组集合为:
    [
    [-1, 0, 1],
    [-1, -1, 2]
    ]

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/3sum
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    /**
     暴力解法
     三次循环
     时间复杂度为O(n^3)
     空间复杂度为o(n),排序之后的数组
     提交LeetCode失败,提示超时
     */
    func threeSum(_ nums: [Int]) -> [[Int]] {
        // Set 集合去重
        var set = Set<[Int]>()
        guard nums.count > 2 else {
            return Array(set)
        }
        let sortedNums =  nums.sorted { (n1, n2) -> Bool in
            n1 < n2
        }
        for i in 0..<sortedNums.count {
            for j in (i+1)..<sortedNums.count {
                for k in (j+1)..<sortedNums.count {
                    if sortedNums[i] + sortedNums[j] + sortedNums[k] == 0 {
                        let list = [sortedNums[i], sortedNums[j], sortedNums[k]]
                        set.insert(list)
                    }
                }
            }
        }
        return Array(set)
    }
    
    /**
     双指针
     三数之和,a + b + c = 0
     先排序数组
     拆解 a + b = -c,假设第一个数就是-c,变成了求两数之和
     使用双指针,一个在头部,一个在尾部,向中间靠拢确定出 a 和 b
     时间复杂度为O(n^2)
     空间复杂度为O(n) 排序后使用另外的数组保存
     执行结果:通过
     执行用时:264 ms, 在所有 Swift 提交中击败了77.39%的用户
     内存消耗:23.4 MB, 在所有 Swift 提交中击败了100.00%的用户
     
     */
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var result = [[Int]]()
        // 过滤数据
        guard nums.count > 2 else {
            return result
        }
        // 排序
        let sortedNums = nums.sorted { (n1, n2) -> Bool in
            n1 < n2
        }
        for i in 0..<sortedNums.count {
            if sortedNums[i] > 0 {
                break
            }
            // 去重
            if i > 0 && sortedNums[i] == sortedNums[i-1] {
                continue
            }
            // 假设第一个值为 目标值,之后进行两数之和计算,头尾双指针
            let target = -sortedNums[i]
            var left = i + 1
            var right = sortedNums.count-1
    
            while left < right {
                if sortedNums[left] + sortedNums[right] == target {
                    let list = [sortedNums[i], sortedNums[left], sortedNums[right]]
                    result.append(list)
                    // 去除头部重复数据
                    while left < right && sortedNums[left] == sortedNums[left+1] {
                        left += 1
                    }
                    // 去除尾部重复数据
                    while left < right && sortedNums[right] == sortedNums[right-1] {
                        right -= 1
                    }
                    left += 1
                    right -= 1
                } else if(sortedNums[left] + sortedNums[right] < target) {
                    left += 1
                } else {
                    right -= 1
                }
            }
        }
        return result
    }
    
    /**
     结合LeetCode上的其他朋友的提交记录进一步优化一些细节
     执行时间比上一个代码减少一些
     执行结果:通过
     执行用时:248 ms, 在所有 Swift 提交中击败了93.97%的用户
     内存消耗:23.8 MB, 在所有 Swift 提交中击败了52.17%的用户
     */
    func threeSum(_ nums: [Int]) -> [[Int]] {
        var result = [[Int]]()
        // 过滤数据
        guard nums.count > 2 else {
            return result
        }
        // 升序 排序
        let sortedNums = nums.sorted { (n1, n2) -> Bool in
            n1 < n2
        }
        // 遍历的最后节点从 count -> count-2 ,
        // i, left=i+1, right=count-1 这种状态才需要处理
        // i=count-1, left=count, right=count,left==count 无需在遍历中处理,直接在此过滤掉
        for i in 0..<sortedNums.count-2 {
            // 排序之后,第一个数大于0,之后全部大于0,没有满足条件的数据
            if sortedNums[i] > 0 {
                break
            }
            // 去重
            if i > 0 && sortedNums[i] == sortedNums[i-1] {
                continue
            }
            // 假设第一个值为 目标值,之后进行两数之和计算,头尾双指针
            let target = -sortedNums[i]
            var left = i + 1
            var right = sortedNums.count-1
    
            while left < right {
                if sortedNums[left] + sortedNums[right] == target {
                    let list = [sortedNums[i], sortedNums[left], sortedNums[right]]
                    result.append(list)
                    // 去除头部重复数据
                    while left < right && sortedNums[left] == sortedNums[left+1] {
                        left += 1
                    }
                    // 去除尾部重复数据
                    while left < right && sortedNums[right] == sortedNums[right-1] {
                        right -= 1
                    }
                    left += 1
                    right -= 1
                } else if(sortedNums[left] + sortedNums[right] < target) {
                    left += 1
                } else {
                    right -= 1
                }
            }
        }
        return result
    }
    
    let nums = [-1,0,1,2,-1,-4]
    threeSum(nums)
    
    

    GitHub:https://github.com/huxq-coder/LeetCode

    相关文章

      网友评论

          本文标题:LeetCode - 15.三数之和 swift

          本文链接:https://www.haomeiwen.com/subject/vcbfjktx.html