算法与编码技巧 加入小组

9个成员 12个话题 创建时间:2018-07-03

Three Sum(三数之和)

发表于2018-07-08 852次查看

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

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

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

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

题目链接:

1. 英文:https://leetcode.com/problems/3sum/description/

2. 中文:https://leetcode-cn.com/problems/3sum/description/

2回复
  • 2楼 wusheng 2018-08-04

    python代码

    这个代码是我没有看Ryan老师的上课视频,结合上节课2sum学习到的双指针知识点写的

    题目看起来很简单,但是这个代码一共花了我4个小时才debug通过leetcode的提交

    之所以debug这么长时间是因为没有想到以下细节问题:

    1.输入数组是两个元素,如[0,0]

    2.输入正好是3元素[0,0,0]

    3.输入数组很长,如[0,0,0,0,0,0,0,0,0,0,0],运行时间过长,无法通过提交

    4.输出结果包含重复的三元素合集

    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            tmp_list=[]
            tmp_dict={}
            if len(nums)<3: return tmp_list
            if len(nums)==3:
                if nums[0]+nums[1]+nums[2]==0:
                    return [nums]
            doublezero=0;
            idx=map(lambda x:x[0],sorted(list(enumerate(nums)),key=lambda x:x[1]))
            for i in range(len(nums)-2):
                if nums[idx[i]] ==0 and nums[idx[i+1]]==0:
                    doublezero+=1
                    continue
                target=-nums[idx[i]]
                left=i+1
                right=len(nums)-1
                while (left<right or left!=right):
                    if nums[idx[left]]+nums[idx[right]]==target:
                        key="".join([str(k) for k in \
                            sorted(set([nums[idx[i]],nums[idx[left]],nums[idx[right]]]))])
                        if not tmp_dict.has_key(key):
                            tmp_list.append([nums[idx[i]],nums[idx[left]],nums[idx[right]]])
                            tmp_dict[key]=None
                        left+=1
                    elif nums[idx[left]]+nums[idx[right]]<target:
                        left +=1
                    elif nums[idx[left]]+nums[idx[right]]>target:
                        right -=1
            if doublezero>=2 and not tmp_dict.has_key('0'):
                tmp_list.append([0,0,0])
            return   tmp_list

    写的不好,请多多指教。

  • 3楼 wusheng 2018-08-08

    Ryan老师的方法好简便,请略过我的代码。。。

发表回复
你还没有登录,请先 登录或 注册!
话题作者
解惑者学院首席讲师