三数之和

之和"/>

三数之和

题目：
 

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

思路：
在忽略存在重复三元数组的情况下，这个题的思路其实变得简单起来，首先我们先对数组进行从小到大的排序，同样从头到尾立一个flag，首先从第一个元素开始，然后设立两个双指针分别指向第二个元素和最后一个元素，这个三个元素分别记为a，b，c，当a确定时加上b和c，如果三数之和sum<0,此时left指针向右移动，如果sum>0,则right指针向左移动，移动的同时不断向二维数组中记录得到的答案。

但是此题关键就在于需要在最后的三元数组中不存在重复的数组，我们就需要对可能出现重复的情况进行讨论，

首先对于a而言，如果出现连续两个数重复的话，容易在第二次相同的a 的结果集中出现重复，所以我们要对第二个重复的进行跳过，在这里我们进行判断的条件就应该是等第一个a匹配完后，第二个a进行判断。

对b和c而言就简单的是遇到重复的数字就continue

代码实现：
 

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
int cmp(const void* ptr1, const void* ptr2) {return *((int*)ptr1) > *((int*)ptr2);
}int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {//开辟ans数组空间int **ans = (int**)malloc(sizeof(int*) * 18000);int ansTop = 0;//若传入nums数组大小小于3，则需要返回数组大小为0if(numsSize < 3) {*returnSize = 0;return ans;}//对nums数组进行排序qsort(nums, numsSize, sizeof(int), cmp);int i;//用for循环遍历数组，结束条件为i < numsSize - 2(因为要预留左右指针的位置)for(i = 0; i < numsSize - 2; i++) {//若当前i指向元素>0，则代表left和right以及i的和大于0。直接breakif(nums[i] > 0)break;//去重：i > 0 && nums[i] == nums[i-1]if(i > 0 && nums[i] == nums[i-1])continue;//定义左指针和右指针int left = i + 1;int right = numsSize - 1;//当右指针比左指针大时进行循环while(right > left) {//求出三数之和int sum = nums[right] + nums[left] + nums[i];//若和小于0，则左指针+1（因为左指针右边的数比当前所指元素大）if(sum < 0)left++;//若和大于0，则将右指针-1else if(sum > 0)right--;//若和等于0else {//开辟一个大小为3的数组空间，存入nums[i], nums[left]和nums[right]int* arr = (int*)malloc(sizeof(int) * 3);arr[0] = nums[i];arr[1] = nums[left];arr[2] = nums[right];//将开辟数组存入ans中ans[ansTop++] = arr;//去重while(right > left && nums[right] == nums[right - 1])right--;while(left < right && nums[left] == nums[left + 1])left++;//更新左右指针left++;right--;}}}//设定返回的数组大小*returnSize = ansTop;*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);int z;for(z = 0; z < ansTop; z++) {(*returnColumnSizes)[z] = 3;}return ans;
}