|
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000
- 105 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https ://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*返回大小为*returnSize的数组。
*数组的大小作为*returnColumnSizes数组返回。
*注意：返回的数组和*columnSizes数组都必须是malloced，假设调用方调用free（）。
1： 快速排序，之后使用双指针遍历对应的位置，求解
2： 主要是在确定了第一个值，后通过双指针的方式，确定出来其余两个值
3： 将结果统计出来
nums = [-1,0,1,2,-1,-4]
快排结果如下：
nums = [ -4, -1, -1, 0, 1, 2]
三指针 ^ ^ ^
| | |
Left Middle indexRight
初始状态 |
遍历 middle 和 indexRight的区间
Left + Middle + indexRight = -4 + -1 + 2 = -3 < 0
Middle移动 一直移动 Middle == -1 , 0 , 1 < 0
Left = -4的没有符合的
************************
移动 Left
nums = [ -4, -1, -1, 0, 1, 2]
^ ^ ^
| | |
Left Middle indexRight
Left + Middle + indexRight = -1 + -1 + 2 = 0 记录结果
************************
移动Middle
nums = [ -4, -1, -1, 0, 1, 2]
^ ^ ^
| | |
Left Middle indexRight
Left + Middle + indexRight = -1 + 0 + 2 > 0 不符合
************************
indexRight
nums = [ -4, -1, -1, 0, 1, 2]
^ ^ ^
| | |
Left Middle indexRight
Left + Middle + indexRight = -1 + 0 + 1 = 0 符合
此时Left等于-1时的结果遍历结束。
************************
移动 Left
nums = [ -4, -1, -1, 0, 1, 2]
^
|
Left
Left和一个Left值一样，会得到相同的结果不符合
************************
移动 Left
nums = [ -4, -1, -1, 0, 1, 2]
^
|
Left
开始遍历只有1种可能 0, 1 ,2 不符合
************************
移动 Left
nums = [ -4, -1, -1, 0, 1, 2]
^
|
Left
Left的值 大于 0了，因为Left是最小的，所以不能三个数相加等于0
直接退出返回
************************
int cmp(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
*returnSize = 0;
if (numsSize < 3)
return NULL;
qsort(nums, numsSize, sizeof(int), cmp);
int **ans = (int **)malloc(sizeof(int *) * numsSize *numsSize);
*returnColumnSizes = (int *)malloc(sizeof(int) * numsSize * numsSize);
int i, j, k, sum;
int indexLeft = 0;
int indexMiddle = 0;
int indexRight = 0;
//快排过后，使用三指针 遍历
//左边遍历到倒数第三位即可
for (indexLeft = 0; indexLeft < numsSize - 2; indexLeft++)
{
if (nums[indexLeft] > 0)
{
//因为是快排的结果，所以如果出现大零的
//后面的值都是大于0的
return ans;
}
//如果值相同 则不需要遍历
if (indexLeft > 0 && nums[indexLeft] == nums[indexLeft - 1])
continue;
indexMiddle = indexLeft + 1;
indexRight = numsSize - 1;
//双指遍历 找到所有的可能
while (indexMiddle < indexRight)
{
sum = nums[indexLeft] + nums[indexMiddle] + nums[indexRight];
if (sum == 0)
{
ans[*returnSize] = (int*)malloc(sizeof(int) * 3);
(*returnColumnSizes)[*returnSize] = 3;
ans[*returnSize][0] = nums[indexLeft];
ans[*returnSize][1] = nums[indexMiddle];
ans[*returnSize][2] = nums[indexRight];
*returnSize += 1;
//过滤相等的值
while (indexMiddle < indexRight && nums[indexMiddle] == nums[++indexMiddle]);
while (indexMiddle < indexRight && nums[indexRight] == nums[--indexRight]);
}
else if (sum > 0)
{
//左边递减
indexRight--;
}
else
{
//右边递增
indexMiddle++;
}
}
}
return ans;
}
int main()
{
int nums[6] = { -1, 0, 1, 2, -1, -4 };
int numsSize = 6;
int i = 0, j = 0;
int returnSize;// 表示返回的二维数组的行数
int **returnColumnSize;// 指向列数组指针的指针
// 注意：列数组在哪我们无从得知，也不需要知道，
// 我们只要知道有个一阶指针指向它就行了，我把它叫做列数组指针
int **ans = threeSum(nums, numsSize, &returnSize, returnColumnSizes);
// &returnSize 引用传值
// 最后一个参数我认为也可以是 int *returnColumnSize，然后传入&returnColumnSizes，效果是一样的
for (i = 0; i < (*returnSize); i++) {
for (j = 0; j < (*returnColumnSize)[i]; j++)
printf("%d", ans[i][j]);
printf("\n");
}
return 0;
}
|