Leetcode 三数之和

解题思路：

1. 排序数组：首先对数组进行排序，以便使用双指针技术来查找三元组。
2. 双指针法：在遍历数组时，遍历固定三元组的第一个元素，然后使用双指针（分别指向剩下数组的头和尾并相向而行，因为下标两两不同）来寻找另外两个元素，使三者之和为零。
3. 去重处理：为了避免重复的三元组，跳过重复的元素。

为什么需要对原始数组进行排序？

在这道题中，对数组进行排序是为了简化解决过程，并有效避免重复结果。排序在解决这类问题时的作用是不可忽视的。下面详细解释为什么排序是必要的，以及不排序会遇到什么样的问题。

1. 简化双指针操作：

排序的一个主要目的是方便使用双指针技巧。在经过排序的数组中，我们可以利用双指针分别从数组的两端开始，来寻找和为 0 的三元组。 排序后，双指针可以轻松地通过调整指针（根据当前和的大小）来决定向哪边移动，从而减少时间复杂度。

如果不进行排序，双指针策略将无法应用，因为在无序的数组中，无法简单判断是否应该移动左指针还是右指针来缩小差距。我们会陷入遍历每一个组合的情况，这样会使时间复杂度增加至 $O(n^3)$，性能远远不如 $O(n^2)$ 的双指针方法。

2. 去重处理：

排序的另一个重要作用是去除重复的三元组。排序后，相同的数字会排在一起，因此在遍历时很容易跳过重复的元素。这个去重过程是通过在遍历中跳过连续相同的元素来实现的。

如果数组没有排序，想要去重就需要额外的数据结构（如哈希表）来存储已经出现的三元组，并且需要进行额外的查找操作，这样就会增加时间和空间的复杂度。

3. 使用排序的例子：

假设我们有一个数组 [-1, 0, 1, 2, -1, -4]，如果不排序，我们会发现所有可能的三元组（假设通过暴力搜索），会包含：

[-1, 0, 1]
[0, -1, 1]
[-1, 2, -1]
[-4, 1, 2]

可以看到，有些三元组（如 [-1, 0, 1] 和 [0, -1, 1]）在不排序的情况下会被计算多次。而排序后，我们可以确保相同的数字只出现一次，并且可以跳过重复的三元组，得到的结果更加简洁。

4. 避免 $O(n^3)$ 的暴力解法：

不排序的情况下，你可以通过三重循环遍历所有的三元组来解决问题，即暴力解法，其时间复杂度是 $O(n^3)$。在实际场景中，如果输入数组较大，这种方法的效率会非常低。通过排序并使用双指针方法，我们可以将时间复杂度优化到 $O(n^2)$。

总结：

虽然不排序也可以通过某些方法找到和为 0 的三元组，但排序有如下显著优势：

1. 使用双指针减少时间复杂度到 $O(n^2)$。
2. 简化了去重逻辑，避免了复杂的查重操作。
3. 排序后方便高效地跳过重复元素。

因此，排序在这道题中是必要的，它使得解决方案更加高效和简单。

注意点：

不仅需要在固定三元组第一个元素时进行脱重处理，同时也需要在双指针移动时，匹配到三元组时对双指针指向的元素进行脱重处理！！

固定三元组第一个元素进行脱重处理时，从第二个元素开始进行脱重判断

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result; //创建一个存储结果的向量sort(nums.begin(), nums.end()); //先对原始数组进行排序for(int i = 0; i < nums.size(); i++) {//然后首先进行去重处理，从第二个元素开始进行判断if(i > 0 && nums[i] == nums[i-1]) continue;//初始化双指针int left = i + 1;int right = nums.size() - 1;//初始完双指针之后，两个指针开始移动，并且移动需要有终止条件，那就是左指针小于右指针while(left < right) {int sum = nums[left] + nums[right] + nums[i];if(sum == 0) {result.push_back({nums[i], nums[left], nums[right]});//这里再次需要去重处理！while(left < right && nums[left] == nums[left+1]) left++;while(left < right && nums[right] == nums[right-1]) right--;left++;//左指针指向的下一个值增大right--;//右指针指向的下一个值减小}else if(sum < 0) {left++;//这里之所以左指针右移, 是因为数组已经经过排序了, 所以右指针已经是当前剩余元素中的最大值了}else {right--;//这里之所以右指针左移, 是因为数组已经经过排序了, 所以左指针已经是当前剩余元素中的最小值了}}}//返回结果return result;}
};

时间复杂度：

• 排序的时间复杂度是 $O(n\log n)$。
• 遍历数组和使用双指针查找的时间复杂度是 $O(n^2)$。
• 因此总的时间复杂度为 $O(n^2)$。

空间复杂度：

• 排序算法使用 $O(\log n)$ 的空间，此外只有常数级别的额外空间，因此空间复杂度为 $O(n)$（不考虑输出结果的空间）。