【leetcode--三数之和】
这道题记得之前做过，但是想不起来了。。总结一下：
函数的主要步骤和关键点：
- 排序：对输入的整数数组
nums进行排序。这是非常重要的，因为它允许我们使用双指针技巧来高效地找到满足条件的三元组。 - 初始化：定义
ans列表来存储所有找到的三元组，并初始化三个指针first、second和third。 - 枚举第一个数：使用
first指针遍历整个数组。为了避免重复的三元组（例如[-1, 0, 1]和[0, -1, 1]），我们需要跳过所有与前一个数相同的数。 - 设置目标和双指针：将目标和
target设置为-nums[first]，然后初始化third指针为数组的最后一个元素的索引。此时，我们需要找到两个数（nums[second]和nums[third]），它们的和等于target。 - 枚举第二个数：使用
second指针从first + 1开始遍历数组。同样地，为了避免重复的三元组，我们需要跳过所有与前一个数相同的数。 - 双指针技巧：当
nums[second] + nums[third] > target时，说明third指向的数太大了，我们需要将third向左移动；否则，我们检查是否找到了一个满足条件的三元组。 - 避免重复：当
second和third相遇或nums[second] + nums[third] == target时，我们需要检查是否找到了一个有效的三元组，并将其添加到ans列表中。然后，我们继续移动second指针，但在这之前，我们需要跳过所有与当前nums[second]相同的数，以避免找到重复的三元组。 - 返回结果：返回存储了所有满足条件的三元组的
ans列表。
改进点：这个算法的时间复杂度是O(n^2)，其中n是数组nums的长度。
-
设 s = nums[first] + nums[first+1] + nums[first+2]，如果 s > 0，由于数组已经排序，后面无论怎么选，选出的三个数的和不会比 s 还小，所以只要 s > 0 就可以直接 break 外层循环了。
-
如果 nums[first] + nums[n-2] + nums[n-1] < 0，由于数组已经排序，nums[first] 加上后面任意两个数都是小于 0 的，所以下面的双指针就不需要跑了。但是后面可能有更大的 nums[first]，所以还需要继续枚举，continue 外层循环。
class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()ans = []n = len(nums)for i in range(n-2):x = nums[i]if i > 0 and x == nums[i-1]:continueif x + nums[i+1] + nums[i+2] > 0:breakif x + nums[-1] + nums[-2] < 0:continuej = i+1k = n-1while j<k:s = x + nums[j] + nums[k]if s < 0:j += 1elif s > 0:k -= 1else:ans.append([x,nums[j],nums[k]])j += 1while j < k and nums[j] == nums[j-1]:j += 1k -= 1while k > j and nums[k] == nums[k+1]:k -= 1return ans