leetcode-三数之和

前言

今天是给自己打零分的自己，表现过于差劲。还是要好好学习呀~明天要注意言行，做到没有弱点。下个星期的周日就是蜜月日了，有点小期待哦，快点来快点来。说点不开心的事吧，不在青协的人觉得青协越来越好了，而留在青协的人越来越不喜欢青协了。呼，有点低迷啊。哄一下我吧，小宝贝。开始刷题吧，蛮久没刷leetcode了，还是要每周刷一下。

题目

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

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

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

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

思路

这道题的思路用到一个比较经典的算法概念，双指针。然后我们引入这样一个想法： A+B+C=0 -> -A = B+C 由此构造一个双指针遍历，而这道题的难点在于，输出的结果中的列表不能重复，而且数字要有小到大，所以肯定需要先对数组进行排序，接下来直接进入代码

代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #先需要对给定列表排序，一是为了方便按题目给定格式输出，而是双指针遍历需要该列表是顺序列表
        nums = sorted(nums)
        re_list = []  
        for i in range(len(nums)):
            # 因为已经排好序，所以第一个数大于0的话，后面三数相加不定大于0
            if nums[i] > 0 :
                break
            # 去除重复结果
            if i > 0 and nums[i] == nums[i-1]:
                continue
            temp = 0 - nums[i]     
            j =  i + 1
            k = len(nums) - 1
            while j < k :
                if nums[j] +nums[k] == temp :
                    # 追加列表
                    re_list.append([nums[i],nums[j],nums[k]])
                    # 去除重复结果
                    while j < k and nums[j] == nums[j+1]: 
                        j += 1
                    while j < k and nums[k] == nums[k-1]: 
                        k -= 1
                    j += 1
                    k -= 1
                else :
                    if nums[j] +nums[k] < temp :
                        j += 1
                    else:
                        k -= 1
        return re_list

总结

加油！我要想想怎么在博客是加一个纪念日推算的东西