【力扣】【Leetcode 15】三数之和｜暴力枚举 | 双指针
给你一个整数数组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 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
参考解法一：暴力三重for循环（存在超时问题）
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; int n = nums.size(); int a, b, c; if (n < 3) return result; sort(nums.begin(), nums.end()); // 只加这一行去重 cout << "["; bool first = true; // 用来控制逗号，不输出多余逗号 for (int i = 0; i < n; i++) { // 去重：i 重复就跳过 if (i > 0 && nums[i] == nums[i-1]) continue; a = nums[i]; for (int j = i + 1; j < n; j++) { // 去重：j 重复就跳过 if (j > i+1 && nums[j] == nums[j-1]) continue; b = nums[j]; for (int k = j + 1; k < n; k++) { // 去重：k 重复就跳过 if (k > j+1 && nums[k] == nums[k-1]) continue; c = nums[k]; if (a + b + c == 0) { if (!first) cout << ","; first = false; // 打印 cout << "[" << a << "," << b << "," << c << "]"; // 存入结果（你原来没存） result.push_back({a, b, c}); } } } } cout << "]" << endl; return result; } };参考解法2：双指针
//快速排序 void qsort(int a[], int left, int right){ int i = left, j = right, flag = a[(left+right)/2], tmp; do { while(a[i] < flag) i++; //左起找比flag大的数 while(a[j] > flag) j--; //右起找比flag小的数 if (i<=j){ tmp = a[i]; a[i] = a[j]; a[j] = tmp; i++; j--; } } while(i <=j); if (left < j) qsort(a, left, j); if (i < right) qsort(a,i,right); } class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; int n = nums.size(); if(n < 3) return result; qsort(&nums[0], 0, n-1); //快速排序nums数组 int left, right; //左右双指针 int a=0, b=0, c=0; for (int i = 0; i<n; i++){ int a = nums[i]; if(i > 0 && nums[i] == nums[i-1]) continue; //不能重复 left = i+1; right = n-1; while (left < right){ //如下写法表示的是把b赋值到了nums[left]的位置，取代了原来的值。 // nums[left] = b; // nums[right] = c; b = nums[left]; c = nums[right]; if (a + b + c == 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 (a + b + c > 0) right--; //大于零,则表示大的数太大了 else if (a + b + c < 0) left++; //小于0，则表示小的数太小了 } } return result; } };完整的（含输入输出的写法，LLM生成）：
#include<iostream> #include<vector> using namespace std; void qsort(int a[], int left, int right){ //数组，起始索引，结束索引 int i = left, j = right, flag = a[(left + right) / 2], tmp; do { while (a[i] < flag) i++; while(a[j] > flag) j--; if (i <= j){ tmp = a[i]; a[i] = a[j]; a[j] = tmp; i++; j--; } } while(i <= j); if (left < j) qsort(a, left, j); if (i < right) qsort(a, i, right); } int main(){ bool flag = ture; //每找到一个三元组就加一个逗号 int n = nums.size(); //输入数组 vector<int> nums; int x; while (cin >> x){ nums.push_back(x); if(cin.get() == '\n') break; //回车即输入完毕 } if (n < 3) return false; qsort(&nums[0],0,n-1); //反正题目说了三元组元素顺序不影响结果，那就随便排 int left, right; int a,b,c; for (int i=0; i<n; i++){ a = nums[i]; if (i <0 && nums[i] == nums[i-1]) continue; //去重 left = i+1; right = n-1; while (left < right){ b = nums[left]; c = nums[right]; if (a+b+c == 0){ if (!flag) cout << ","; flag = flase; cout << "[" << a << "," << b << "," << c <<"]"; } } } }
