算法题:三数之和

题目来源于力扣

理论基础

哈希表

三数之和

题目描述

三数之和

示例

给定 [-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
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!