leecode100题-双指针-三数之和

给你一个整数数组 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] 。

解析：

先对数组排序，设一非递减的数组示例和初始三指针位置及名字如下所示。

固定i，即可转换为寻找满足 nums[l]+nums[r]=−nums[i] 的三元组，因为不能包含重复的三元组，以下两个三元组只能取一个，而后我们再考虑其是否满足 nums[l]+nums[r]=−nums[i]。

移动指针的时候，需要规避连续的重复元素

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//排序c// 待返回的三元组vector<vector<int>> triples;for(int i = 0; i < nums.size(); i++){// 检测重复的 nums[i]if(i > 0 && nums[i] == nums[i-1]) continue;int l = i + 1;int r = nums.size() - 1;while(l < r) {// 检测重复的 nums[l] 并防止越界while(l > i + 1 && l < nums.size() && nums[l] == nums[l-1]) l++;// 检测重复的 nums[r] 并防止越界while(r < nums.size() - 1 && r > i && nums[r] == nums[r+1]) r--;// 防止 l, r 错位if(l >= r) break;if(nums[i] + nums[l] + nums[r] > 0) r--;else if(nums[i] + nums[l] + nums[r] < 0) l++;else {// nums[l] + nums[r] == nums[i], 三元组符合，添加入结果triples.push_back({nums[i], nums[l], nums[r]});l++; r--;}}}return triples;}
};

int cmp(const void* pa, const void* pb){int a=*(int*)pa;int b=*(int*)pb;return a>b?1:-1;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){int base=100;//数组的初始长度，可更改//初始化处理返回值，二维数组的大小和保存每一个一维数组大小的数组的空间保持一致int** res=(int**)malloc(sizeof(int*)*base);*returnColumnSizes=(int*)malloc(sizeof(int)*base);*returnSize=0;int i,j,k;//排序qsort(nums,numsSize,sizeof(int),cmp);for(i=0;i<numsSize;i++){//先确定第三个数的值，再对剩下的两个数进行两数之和的操作//若本次的第三个数与上一次的情况相同，则跳过这个数if(i>0&&nums[i]==nums[i-1])continue;//给定nums[i]，以j，k作为双指针进行两数之和操作j=i+1;k=numsSize-1;while(j<k){int sum=nums[i]+nums[j]+nums[k];if(sum==0){//刚好遇见符合要求的三元组//申请返回值二维数组的空间res[*returnSize]=(int*)malloc(sizeof(int)*3);//每一个数组大小都为3(*returnColumnSizes)[*returnSize]=3;//给申请的空间赋值res[*returnSize][0]=nums[i];res[*returnSize][1]=nums[j];res[*returnSize][2]=nums[k];//二维数组的行数加1(*returnSize)++;//如果二维数组的大小达到初始设定的行数，则进行空间扩容if(*returnSize==base){base*=2;res=(int**)realloc(res,sizeof(int*)*base);*returnColumnSizes=(int*)realloc(*returnColumnSizes,sizeof(int)*base);}//记录符合要求的两个数，进行去重int num1=nums[j],num2=nums[k];while(nums[j]==num1&&j<k)j++;while(nums[k]==num2&&j<k)k--;}//若三个数之和小于0，则左边的指针右移else if(sum<0)j++;//若三个数的之和大于0，则右边的指针往左移else k--;}}return res;
}