Login light

https://leetcode-cn.com/problems/3sum/

错误解法,超时

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #排序
        nums.sort()
        ret = []
        for i in range(0, len(nums) - 2):
            #nums[i]不可能大于0
            if nums[i] > 0:
                break
            for j in range(i + 1, len(nums) - 1):
                #值不可能存在,跳出
                if nums[i] + nums[j] > 0:
                    break
                #当前ij的值已存在,跳出
                if ret != [] and (nums[i],nums[j]) in [x[:2] for x in ret]:
                    continue
                val = abs(nums[i] + nums[j])
                for k in range(j + 1, len(nums)):
                    if val == nums[k]:
                        ret.append((nums[i],nums[j],nums[k]))
                        break
        return ret

正确解法:

  1. 先确定第一个合法数字,不能为>0的数。
  2. 判断是否和上一位相同,若相同代表已经判断过,跳出。
  3. 从当前位置的下一位和列表末尾向中间逼近,通过判断三个数的和确定是左侧还是右侧向中间移动,直到left=right
  4. 判断成功后,如果发现下一位与当前位置相同,则跳过。

时间复杂度:Oleft(n^{2}right)O(n
2
),数组排序 O(N log N)O(NlogN),遍历数组 Oleft(nright)O(n),双指针遍历 Oleft(nright)O(n),总体 O(N log N)+Oleft(nright)*Oleft(nright)O(NlogN)+O(n)∗O(n),Oleft(n^{2}right)O(n
2
)
空间复杂度:O(1)O(1)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #排序
        nums.sort()
        #返回值
        ret = []
        lenNums = len(nums)
        for i in range(lenNums):
            val = nums[i]
            #i的值>0 无解
            if val > 0:
                break
            #判断是否和上一位重复
            if i > 0 and val == nums[i-1]:
                continue
            l = i + 1
            r = lenNums - 1
            while l < r:
                #末位<0 无解
                if nums[r] < 0:
                    break
                if val + nums[l] + nums[r] == 0:
                    ret.append((
                        val , nums[l] , nums[r]
                    ))
                    #判断下一位是否和当前相同,若相同则跳过
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    #寻找下一个
                    r -= 1
                    l += 1
                elif val + nums[l] + nums[r] > 0:
                    #当前值偏大,右侧想左移动
                    r -= 1
                else:
                    #当前值偏小,左侧向右移动
                    l += 1
        return ret