松江泗泾网站建设,公司电子商务网站建设策划书,域名普通词注册,大网站用wordpress吗题目#xff1a;
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意#xff1a;答案中不可以包含重…题目
给你一个整数数组 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首先从第一个元素开始然后设立两个双指针分别指向第二个元素和最后一个元素这个三个元素分别记为abc当a确定时加上b和c如果三数之和sum0,此时left指针向右移动如果sum0,则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;
}
