leetcode代码记录(三数之和

简介: leetcode代码记录(三数之和

1. 题目:

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1:

输入:nums = [-1,0,1,2,-1,-4]

输出:[[-1,-1,2],[-1,0,1]]

解释:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]

输出:[]

解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]

输出:[[0,0,0]]

解释:唯一可能的三元组和为 0 。

2. 我的代码:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 记录多个结果
        result = []
        # 左右指针
        min_p = 0
        max_p = len(numbers) - 1

        # 左右指针向中间靠拢
        while min_p < max_p:
            sum_num = numbers[min_p] + numbers[max_p]
            if sum_num < target:
                min_p += 1
            elif sum_num > target:
                max_p -= 1
            else:
                result.append([numbers[min_p], numbers[max_p]])
                while min_p < max_p and numbers[min_p] == numbers[min_p + 1]:
                    min_p += 1
                while min_p < max_p and numbers[max_p] == numbers[max_p - 1]:
                    max_p -= 1

                min_p += 1
                max_p -= 1


        return result

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        # 结果
        result = []
        # 排序
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] > 0:
                break
            if(i>0 and nums[i]==nums[i-1]):
                continue

            k = self.twoSum(nums[i + 1:], -nums[i])
            if k != []:
                for k_item in k:
                    num1, num2 = k_item
                    result.append([num1, num2, nums[i]])
            else:
                continue
                
        return result

两数相加函数的重新利用

其中:

while min_p < max_p and numbers[min_p] == numbers[min_p + 1]:
    min_p += 1
while min_p < max_p and numbers[max_p] == numbers[max_p - 1]:
    max_p -= 1

这部分是左右指针的改进版,可以防止重复值。这个不能放太早,不然会错过类似于0 + 0 = 0的情况,因此,放在了判定为加和结果正确的情况下再去除重复值。

并且改造了部分两数相加的代码,使得其可以记录多种结果,结果放在列表中,类似于1 = 2 + -1,1 = 3 + -2。

三数相加的逻辑部分

  1. 先排序,为了利用左右指针:
    sort的时间复杂度为O(n log n)
  2. 循环每一个元素,查看在此元素右边所有元素组成的列表中,是否有两数和为此元素的负值(即是三数相加为0)。为什么是元素右边所有元素呢,因为没必要看左边的了,因为左边的情况在之前的迭代中已经考虑过了。
  3. 这里也需要进行去重,nums[i]==nums[i-1]时候即可跳过本次循环。这里需要i>0,为了防止三个元素长度的[0,0,0]被输出为[]

时间复杂度总共为O(n log n) + O(n2) = O(n2)

目录
相关文章
|
6月前
力扣-2029-石子游戏-‘屎山’代码
力扣-2029-石子游戏-‘屎山’代码
48 3
|
7月前
|
算法
leetcode代码记录(全排列 II
leetcode代码记录(全排列 II
57 4
|
7月前
leetcode代码记录(最长回文子串
leetcode代码记录(最长回文子串
49 2
|
7月前
|
算法
leetcode代码记录(寻找两个正序数组的中位数
leetcode代码记录(寻找两个正序数组的中位数
50 2
|
7月前
|
算法
leetcode代码记录(全排列
leetcode代码记录(全排列
65 1
|
7月前
|
索引
leetcode代码记录(Z 字形变换
leetcode代码记录(Z 字形变换
49 1
|
7月前
leetcode代码记录(回文数
leetcode代码记录(回文数
54 1
|
7月前
leetcode代码记录(两数之和
leetcode代码记录(两数之和
46 1
|
7月前
|
机器学习/深度学习
leetcode代码记录(旋转图像
leetcode代码记录(旋转图像
43 0
|
7月前
|
索引
leetcode代码记录(最长公共子序列
leetcode代码记录(最长公共子序列
34 0