【力扣hot100】【Leetcode 15】三数之和｜暴力枚举 双指针 算法笔记及打卡（14/100）

【力扣】【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: vectorvectorint threeSum(vectorint nums) { vectorvectorint 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 i1 nums[j] nums[j-1]) continue; b nums[j]; for (int k j 1; k n; k) { // 去重k 重复就跳过 if (k j1 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[(leftright)/2], tmp; do { while(a[i] flag) i; //左起找比flag大的数 while(a[j] flag) j--; //右起找比flag小的数 if (ij){ 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: vectorvectorint threeSum(vectorint nums) { vectorvectorint result; int n nums.size(); if(n 3) return result; qsort(nums[0], 0, n-1); //快速排序nums数组 int left, right; //左右双指针 int a0, b0, c0; for (int i 0; in; i){ int a nums[i]; if(i 0 nums[i] nums[i-1]) continue; //不能重复 left i1; 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[left1]) 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生成#includeiostream #includevector 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(); //输入数组 vectorint 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 i0; in; i){ a nums[i]; if (i 0 nums[i] nums[i-1]) continue; //去重 left i1; right n-1; while (left right){ b nums[left]; c nums[right]; if (abc 0){ if (!flag) cout ,; flag flase; cout [ a , b , c ]; } } } }