做网站一个月可以赚多少钱,衡水建设投资集团网站,优秀网站开发公司,网站建设的平面设计题目描述
给你一个整数数组 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 。
提示
3 nums.length 3000 -10^5 nums[i] 10^5
题解
快排 双指针法 代码
/*** 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 a comparison function for qsort to sort integers in ascending order
int cmp(const void *a, const void *b)
{return *(int*)a - *(int*)b;
}// Function to find all unique triplets that sum up to zero
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{*returnSize 0; // Initialize the return size to 0if(numsSize 3)return NULL; // If the input array has less than 3 elements, return NULL as no triplet can be formedqsort(nums, numsSize, sizeof(int), cmp); // Sort the input array in ascending order using the custom comparison function// Allocate memory for the 2D array to store the triplets and their sizesint **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;// Use three pointers to traverse the sorted array and find triplets that sum up to zerofor (indexLeft 0; indexLeft numsSize - 2; indexLeft){if (nums[indexLeft] 0) {// If the current element is greater than 0, no triplet can sum up to zero, return the result/* if nums[indexLeft] is greater than 0, * the function immediately returns ans . * In this case, ans will be returned without any modifications or additional calculations. * The ans variable is a pointer to a 2D array of integers,* and at that point in the code, it would be returned as it is, * without any triplets being calculated or added to it.*/return ans;}// Skip duplicate values/* the keyword continue is used within a loop after a condition is met. * When continue is encountered, * it causes the program flow to immediately jump to the next iteration of the loop * without executing the remaining code within the loop for the current iteration.* This helps in avoiding processing duplicate elements and * ensures that only unique elements are considered during the loop execution. */if (indexLeft 0 nums[indexLeft] nums[indexLeft - 1])continue;indexMiddle indexLeft 1;indexRight numsSize - 1;// Use two pointers to find all possible tripletswhile (indexMiddle indexRight){sum nums[indexLeft] nums[indexMiddle] nums[indexRight];if (sum 0){// If the sum is zero, store the triplet in the ans arrayans[*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;// Skip duplicate values// This step is crucial to avoid considering the same combination of elements multiple times and ensures that only unique triplets are recorded. while (indexMiddle indexRight nums[indexMiddle] nums[indexMiddle]);while (indexMiddle indexRight nums[indexRight] nums[--indexRight]);}else if (sum 0){// If the sum is greater than zero, decrement the right pointerindexRight--;}else{// If the sum is less than zero, increment the middle pointerindexMiddle;}}}return ans; // Return the 2D array containing the unique triplets
}作者我自横刀向天笑 链接https://leetcode.cn/problems/3sum/solutions/1211127/san-shu-zhi-he-cyu-yan-xiang-jie-chao-ji-08q2/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
