难度中等5530收藏分享切换为英文接收动态反馈
给你一个整数数组 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
这次还算可以 时间在c语言里面领先百分之96 内存领先百分之93
先简要介绍一下我的思路，我的思路是一个渐变的过程，他在不断修改，不断进步
但有些时候要思考一个问题看上去合理的行为不一定能快，根据测试集的变化看似变快的思路其实会降低时间，但这个思路我们要有。至于到底是怎么回事，请耐下心接着看
//我的第一想法是穷举，但似乎时间复杂度会有点大
//看一些大佬的题解以后做出如下总结(同时在做题的时候补充了一下自己的想法 做出了一些改进)
//我自认为我的剪枝应该做到了极致
//1.大部分用的都是排序+双指针
//排序是去重的一个前提，只有整个数组是有序数组
//我们才能跳过相同数据，排序我用的是堆排序
//2.双指针有多重优化 方式：
//（错误存疑）在有序数组的前提下，第一个first——left跳过相同
//在有序数组的前提下，如果i,i+1,i+2个和大于0可以结束
//在有序数组的前提下，如果第i个与n-1,n-2和小于0说明i不够大 i要++，用continue减少不必要的循环
//在有序数组的前提下，找到合适的解后要用for循环跳过等价解
//在有序数组的前提下，找到解不合适需要跳过相同解 如果过大 third跳过相同解 反之second跳过相同解
这个是不是看上去特别合理，但是因为测试集没有那种解不对且连着出现好几相同的需要跳过的，所以while循环过多的判断反而让时间耗费变多，所以我把那两句话注释掉了（就是else if mid++ else right--里面的哪两个句子）
//3.当我做完陷入自我满足时我又想到一个新方法我只需要一个o（n）就可以避免如此复杂的逻辑
//去掉nums数组里面的相同数据似乎会节省很多时间，但是还可能出现一些问题（我猜测会出问题）
//万一出问题比如某些特解例子会因为我把相同数据去的太多了比如-1 -1 2 这种例子直接丢失了
//因为我把-1直接搞没了，回头思考我是不是剪枝剪疯了 我觉得对于第一个数据不应该跳过相同数据
//吓得我回头标注（错误存疑），问题在于如果向右去重会把-1,-1，2抹去，而向左去重如果在第二个位置遇到-1 我跳过不会省略-1，-1,2这种情况，因为第一个-1时已经把-1，-1,2找到存起来了
//在有序数组的前提下，第一个first——left必须向左去重才能避免-1，-1,2的问题
/**
* 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().
*/
#define size 10
void Swap(int *num, int i, int j)
{
int temp;
temp = num[i];
num[i] = num[j];
num[j] = temp;
}
// 最大堆调整
void Heapify(int *num, int len, int k)
{
if (k < len)
{
int root = k; // 根结点
int lchild = 2*k + 1; // 左孩子结点
int rchild = 2*k + 2; // 右孩子结点
// 查找左右孩子结点中的最大结点
if (lchild < len && num[root] < num[lchild])
{
root = lchild;
}
if (rchild < len && num[root] < num[rchild])
{
root = rchild;
}
// 交换最大结点到根结点
if (root != k)
{
Swap(num, root, k);
// 每次交换都可能影响到对应孩子结点子树的顺序
// 所以需要对交换后的孩子结点子树进行最大堆调整
Heapify(num, len, root);
}
}
}
// 创建最大堆
void CreateHeap(int *num, int len)
{
// 最后一个结点下标
int last = len - 1;
// 最后一个结点的父结点下标
int parent = (last - 1) / 2;
// 从最后一个结点的父结点到根结点，依次进行最大堆调整
for (int i = parent; i >= 0; i--)
{
Heapify(num, len, i);
}
}
// 堆排序
void HeapSort(int *num, int len)
{
// 创建最大堆并进行最大堆调整
CreateHeap(num, len);
printf("最大堆调整!\n");
// 依次取出根结点（最大值）
for (int i = len - 1; i >= 0; i--)
{
// 将最大堆的根结点（最大值）换到最后一个结点
Swap(num, i, 0);
// 交换后二叉树的根结点发生了改变，故还需对根结点做最大堆调整（已交换的末尾结点不参与调整）
// 而此时根结点小于所有父结点，因而在调整时只需考虑最大孩子的分支即可
Heapify(num, i, 0);
}
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
int base=300; //数组的初始长度，可更改
int** a=(int**)malloc(sizeof(int*)*base);
*returnColumnSizes=(int*)malloc(sizeof(int)*base);
*returnSize=0; //初始化
int i,j,k=0,mid,right,temp;
HeapSort(nums,numsSize);
for(i=0;i<numsSize-2;i++){
if(i>0&&nums[i]==nums[i-1]){continue;} //对i向左去重，(向右会忽略-1，-1，2)
if(nums[i]+nums[i+1]+nums[i+2]>0)//在有序数组的前提下，如果i,i+1,i+2个和大于0可以结束
{
break;
}
if(nums[i]+nums[numsSize-1]+nums[numsSize-2]<0)
{
continue;
}
mid=i+1;right=numsSize-1; //定义双指针
while(mid<right){
if(nums[i]+nums[mid]+nums[right]==0){
a[*returnSize]=(int*)malloc(sizeof(int)*3); //每一个数组大小都为3
(*returnColumnSizes)[*returnSize]=3; //给申请的空间赋值
a[*returnSize][0]=nums[i];
a[*returnSize][1]=nums[mid++];
a[*returnSize][2]=nums[right--];
(*returnSize)++; //行自增
while(nums[mid]==nums[mid-1]&&mid<right){mid++;}
while(nums[right]==nums[right+1]&&mid<right){right--;}
if(*returnSize==base){
base*=2;
a=(int**)realloc(a,sizeof(int*)*base);
*returnColumnSizes=(int*)realloc(*returnColumnSizes,sizeof(int)*base);
}//如果二维数组的大小达到初始设定的行数，则进行空间扩容
}//找到目标数组
else if(nums[i]+nums[mid]+nums[right]<0)
{
mid++;
//while(nums[mid]==nums[mid-1]&&mid<right){mid++;}
}
else
{
right--;
//while(nums[right]==nums[right+1]&&mid<right){right--;}
}
}
}//i遍历最小的数，mid从i+1开始，寻找中间的数，right为右指针
return a;
}