【leetcode--三数之和】

这道题记得之前做过，但是想不起来了。。总结一下：

函数的主要步骤和关键点：

1. 排序：对输入的整数数组nums进行排序。这是非常重要的，因为它允许我们使用双指针技巧来高效地找到满足条件的三元组。
2. 初始化：定义ans列表来存储所有找到的三元组，并初始化三个指针first、second和third。
3. 枚举第一个数：使用first指针遍历整个数组。为了避免重复的三元组（例如[-1, 0, 1]和[0, -1, 1]），我们需要跳过所有与前一个数相同的数。
4. 设置目标和双指针：将目标和target设置为-nums[first]，然后初始化third指针为数组的最后一个元素的索引。此时，我们需要找到两个数（nums[second]和nums[third]），它们的和等于target。
5. 枚举第二个数：使用second指针从first + 1开始遍历数组。同样地，为了避免重复的三元组，我们需要跳过所有与前一个数相同的数。
6. 双指针技巧：当nums[second] + nums[third] > target时，说明third指向的数太大了，我们需要将third向左移动；否则，我们检查是否找到了一个满足条件的三元组。
7. 避免重复：当second和third相遇或nums[second] + nums[third] == target时，我们需要检查是否找到了一个有效的三元组，并将其添加到ans列表中。然后，我们继续移动second指针，但在这之前，我们需要跳过所有与当前nums[second]相同的数，以避免找到重复的三元组。
8. 返回结果：返回存储了所有满足条件的三元组的ans列表。

改进点：这个算法的时间复杂度是O(n^2)，其中n是数组nums的长度。

1. 设 s = nums[first] + nums[first+1] + nums[first+2]，如果 s > 0，由于数组已经排序，后面无论怎么选，选出的三个数的和不会比 s 还小，所以只要 s > 0 就可以直接 break 外层循环了。

2. 如果 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