菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
0
0

算法题:三数之和

原创
05/13 14:22
阅读数 457

理论基础

哈希表

三数之和

题目描述

三数之和

示例

给定 [-1,0,1,2,-1,-4], target=0

解题思路

  1. 暴力解法 O (N^3)

  2. a+b+c=0 O(N^2)

  3. 双指针

Python 解法

# a+b+c=0
def threeSum(self, nums):
    if len(nums) < 3:
        return []
    nums.sort()
    res = set()
    for i, v in enumerate(nums[:-2]):
        if i >= 1 and v == nums[i-1]:
            continue
        d = {}
        for x in nums[i+1:]:
            if x not in d:
                d[-v-x] = 1
            else:
                res.add((v, -v-x, x))

    return map(list, res)

# 双指针
def threeSum(self, nums):
    res = []
    nums.sort()
    for i in xrange(len(nums)-2):
        if i > 0 and nums[i] == nums[i-1]:
            cintinue
        l, r = i+1, len(nums)-1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0: l += 1
            elif s > 0: r -= 1
            else:
                res.append((nums[i], nums[l], nums[r]))

                # 判重处理
                while l < r and nums[l] == nums[l+1]:
                    l += 1
                while l < r and nums[r] == nums[r-1]:
                    r -= 1
                l += 1; r -= 1
    return res

发表评论

0/200
0 点赞
0 评论
收藏
为你推荐 换一批