每日一道算法题--leetcode 15--三数之和--python-白红宇

【题目描述】

【代码思路】

【一】 先说一种暴力思路，会发生超时。

首先想到的就是三层for循环的暴力方式，题干要求结果中的三元组不能重复，因此先排序后三层循环，三层循环的时候i之前的j不再遍历，j之前的k不再遍历,一直都是向后找的状态。

nums.sort()length=len(nums)res=[]for i in range(length):    for j in range (i+1,length):        for k in range(j+1,length):复制代码

然后对三个元素求和，再判断一下res结果list中是否已经有了这个三元组，因为已经排序过了，此时判断的时候直接 if [nums[i],nums[j],nums[k]] in res就可以，如果和为0并且结果中不含，则加入到结果列表中。

sum=nums[i]+nums[k]+nums[j]if sum==0 and not [nums[i],nums[j],nums[k]] in res:    res.append([nums[i],nums[j],nums[k]])复制代码

【暴力思路完整源代码】

class Solution(object):    def threeSum(self, nums):                        """        :type nums: List[int]        :rtype: List[List[int]]        """        nums.sort()        length=len(nums)        res=[]        for i in range(length):            for j in range (i+1,length):                for k in range(j+1,length):                    sum=nums[i]+nums[k]+nums[j]                    if sum==0 and not [nums[i],nums[j],nums[k]] in res:                        res.append([nums[i],nums[j],nums[k]])        return res复制代码

【二】 优化后思路，类似一层循环，循环内实现二分查找，查找条件是 nums[left]+nums[right]==-nums[i]

优化思路就要抓住和为0这个点，排序过后，左指针指向i+1较小,右指针指向length-1较大，如果和大于0了，说明右指针的值太大，右指针需要左移；如果和小于0了，说明左指针的值太小，左指针需要右移；如果和为0，则保存起来，再左右指针同时移动，左指针右移，右指针左移，这样就比暴力遍历时间复杂度低。为了避免对重复数值的操作，有两次避免重复的操作，见下方代码备注处。 【优化源代码】

class Solution(object):    def threeSum(self, nums):                        """        :type nums: List[int]        :rtype: List[List[int]]        """        nums.sort()        res =[]        for i in range(len(nums)):            if i == 0 or nums[i]>nums[i-1]:            #如果nums[i]和上一次循环的nums[i]相等，则不执行此次循环，一次避免重复                l = i+1                r = len(nums)-1                while l < r:                    s = nums[i] + nums[l] +nums[r]                    if s ==0 :                        res.append([nums[i],nums[l],nums[r]])                        l +=1                        r -=1                        while r>l and nums[l]==nums[l-1]:                        #如果左指针指向的元素与移动前相同，则继续右移直至不再相等，二次避免重复;右指针同理。                            l+=1                        while r>l and nums[r]==nums[r+1]:                            r-=1                    elif s>0:                        r -=1                    else :                        l +=1        return res复制代码