[算法刷题]双指针解三数之和问题

> Problem: 15. 三数之和

文章目录

• ​​> Problem: [15. 三数之和](https://leetcode.cn/problems/3sum/description/)​​

• ​​思路​​
• ​​解题方法​​
• ​​复杂度​​
• ​​Code​​

思路

这道题本身需要注意的是可能存在重复的解，python对于这种list中嵌套list的没有办法使用set进行去重，估计是因为list没办法用hashtype的形式表达吧。因为set是需要将数据以key：value的形式进行表达的，所以最终表达的时候还是比较困难的。

解题方法

这里解题的时候还是考虑 双指针的解法。为了提高效率，我们需要对预处理的数组进行sorted。这样能够加快我们的处理速度。
对于输入数据的长度小于3或者是没有负数的数据，我们应当给出特解来提高程序执行速度。

复杂度

• 时间复杂度:

添加时间复杂度, 示例：

• 空间复杂度:

添加空间复杂度, 示例：

Code

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        res_list = []

        for index in range(0,len(nums)):
            if nums[index] > 0:
                break
            if len(nums) < 3:
                break

            L = index + 1
            R = len(nums) - 1
            while L < R:
                if nums[index] + nums[L] + nums[R] == 0:
                    item = [nums[index],nums[L],nums[R]]
                    if item not in res_list:
                        res_list.append(item)
                    while L<R and nums[L] == nums[L+1]:
                        L = L + 1 
                    while L < R and nums[R] == nums[R-1]:
                        R = R - 1
                    L = L + 1
                    R = R - 1

                elif nums[index] + nums[L] + nums[R] > 0:
                    R = R - 1
                elif nums[index] + nums[L] + nums[R] < 0:
                    L = L + 1
        return res_list