LeetCode hot 100—三数之和
题目
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例
示例 1：
输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]解释：nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1]输出：[]解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0]输出：[[0,0,0]]解释：唯一可能的三元组和为 0 。
分析
排序+暴力枚举
首先对输入数组 nums 进行排序，这样可以让我们更容易地处理和剪枝，避免重复的三元组。再通过三重循环遍历所有可能的三元组组合，并检查其和是否为 0。
时间复杂度：O(+
)
空间复杂度：O(1)
class Solution {public: vector<vector> threeSum(vector& nums) { vector<vector> result; int n = nums.size(); // 排序，方便去重 sort(nums.begin(), nums.end()); // 遍历每个元素，作为三元组的第一个数 for (int i = 0; i 0 && nums[i] == nums[i - 1]) continue; // 使用第二个循环找出第二个数 for (int j = i + 1; j i + 1 && nums[j] == nums[j - 1]) continue; // 使用第三个数来完成三元组 for (int k = j + 1; k j + 1 && nums[k] == nums[k - 1]) continue; // 判断是否为零和 if (nums[i] + nums[j] + nums[k] == 0) { result.push_back({nums[i], nums[j], nums[k]}); } } } } return result; }};排序+双指针
降低复杂度，就应该要减少循环层。可以观察到，第一重循环固定时，二三重循环本质上在枚举数组中的两个元素时，随着第一个元素的递增，第二个元素应该是递减的，那么就可以使用双指针的方法。这样通过外层循环固定第一个数 a，在剩下的部分使用双指针方法查找另外两个数 b 和 c，满足 a + b + c = 0，将内层的两层循环转化为一层。
时间复杂度：O(+
)
空间复杂度：O(1)
class Solution {public: vector<vector> threeSum(vector& nums) { vector<vector> result; int n = nums.size(); // 排序，方便使用双指针 sort(nums.begin(), nums.end()); // 遍历每个元素作为三元组的第一个数 for (int i = 0; i 0 && nums[i] == nums[i - 1]) continue; int target = -nums[i]; // 目标值变为 -nums[i] int left = i + 1, right = n - 1; // 使用双指针查找剩下的两个数 while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { 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 < target) { left++; // 需要增大和，所以左指针右移 } else { right--; // 需要减小和，所以右指针左移 } } } return result; }};知识充电
sort() 排序函数
sort() 函数专门用来对容器或普通数组中指定范围内的元素进行排序，排序规则默认以元素值的大小做升序排序。如果是自定义类型，sort() 会调用自定义的 < 运算符来比较元素的大小。除了默认的升序排序，sort() 也可以使用自定义的比较函数来指定排序规则，可以传递一个比较函数或者一个函数对象，来定义排序顺序（如降序或者按其他条件排序）。
//自定义降序排序#include #include #include bool compare(int a, int b) { return a > b; // 降序排序}int main() { std::vector nums = {4, 2, 7, 1, 9, 3}; // 使用自定义的比较函数进行降序排序 std::sort(nums.begin(), nums.end(), compare); for (int num : nums) { std::cout << num << \" \"; } return 0;}//按成绩降序排序：成绩高的排在前面。//如果成绩相同，则按年龄升序排序：成绩相同的情况下，年龄小的排在前面。//如果成绩和年龄都相同，则按姓名的字典顺序升序排序：成绩和年龄都相同的情况下，按名字的字典顺序排。#include #include #include #include class Student {public: std::string name; int age; int score; // 构造函数 Student(std::string name, int age, int score) : name(name), age(age), score(score) {}};// 自定义比较函数bool compare(const Student& a, const Student& b) { // 按成绩降序排列 if (a.score != b.score) { return a.score > b.score; } // 如果成绩相同，按年龄升序排列 if (a.age != b.age) { return a.age < b.age; } // 如果成绩和年龄都相同，按姓名的字典顺序升序排列 return a.name < b.name;}int main() { std::vector students = { {\"Alice\", 20, 85}, {\"Bob\", 22, 90}, {\"Charlie\", 20, 85}, {\"David\", 22, 85}, {\"Eva\", 22, 90}, {\"Frank\", 20, 90} }; // 使用自定义比较函数进行排序 std::sort(students.begin(), students.end(), compare); // 打印排序后的学生信息 for (const auto& student : students) { std::cout << student.name << \" \" << student.age << \" \" << student.score << std::endl; } return 0;}sort() 不是稳定的，即如果有两个元素相等，它们的相对顺序在排序后可能发生变化。如果需要稳定排序，可以使用 stable_sort()。
