LeetCode Hot100(7.三数之和）

7.三数之和题目给你一个整数数组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 排序时间复杂度为 O(NlogN)。固定 3 个指针中最左最小元素的指针 k双指针 ij 分设在数组索引 (k,len(nums)) 两端。双指针 i , j 交替向中间移动记录对于每个固定指针 k 的所有满足 nums[k] nums[i] nums[j] 0 的 i,j 组合当 nums[k] 0 时直接break跳出因为 nums[j] nums[i] nums[k] 0即 3 个元素都大于 0 在此固定指针 k 之后不可能再找到结果了。当 k 0且nums[k] nums[k - 1]时即跳过此元素nums[k]因为已经将 nums[k - 1] 的所有组合加入到结果中本次双指针搜索只会得到重复组合。ij 分设在数组索引 (k,len(nums)) 两端当i j时循环计算s nums[k] nums[i] nums[j]并按照以下规则执行双指针移动当s 0时i 1并跳过所有重复的nums[i]当s 0时j - 1并跳过所有重复的nums[j]当s 0时记录组合[k, i, j]至res执行i 1和j - 1并跳过所有重复的nums[i]和nums[j]防止记录到重复组合。代码class Solution { public: vectorvectorint threeSum(vectorint nums) { sort(nums.begin(),nums.end()); vectorvectorint ans; for(int k0;knums.size();k){ if(nums[k]0){break;} if(k0nums[k]nums[k-1]){continue;} int lk1,rnums.size()-1; while(lr){ int snums[k]nums[l]nums[r]; if(s0){ r--; while(lrnums[r1]nums[r]){ r--; } } else if(s0){ l; while(lrnums[l-1]nums[l]){ l; } } else{ ans.push_back({nums[k],nums[l],nums[r]}); l; r--; while(lrnums[l-1]nums[l]){l;} while(lrnums[r1]nums[r]){r--;} } } } return ans; } };