subject ：

Give you a containing n An array of integers nums, judge nums Are there three elements in the a,b,c , bring a + b + c = 0 ? Please find out all and for 0
Triple without repetition .
be careful ： The answer cannot contain duplicate triples .

Example 1：

input ：nums = [-1,0,1,2,-1,-4]
output ：[[-1,-1,2],[-1,0,1]]

Example 2：

input ：nums = []
output ：[]

Example 3：

input ：nums = [0]
output ：[]

Tips ：

0 <= nums.length <= 3000
- 1 0 5 10^5 105 <= nums[i] <= 1 0 5 10^5 105

Problem solving code ：
/** * 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(). */ void exch(
int *x, int *y) { int temp = *x; *x = *y; *y = temp; } int getIndex(int arr[],
int left, int right) { int refer = arr[left]; int index = left; while(left <
right) { while((arr[right] > refer) && (left < right)) right--; while((arr[left]
<= refer) && (left < right)) left++; exch(&arr[left], &arr[right]); } exch(&arr[
left], &arr[index]); return left; } int quickSort(int arr[], int left, int right
) { if(left < right) { int index = getIndex(arr, left, right); quickSort(arr,
left, index - 1); quickSort(arr, index + 1, right); } return 0; } // Above is the quick sort code
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes
){ // I'll give it when I come up returnSize assignment The number of rows used to represent the returned result It should be used to traverse the array // If written in return NULL after
returnSize If there is no value, an error will be reported when traversing *returnSize = 0; if(numsSize < 3) return NULL; // Sort array
The premise of double fingering is sorting quickSort(nums, 0, numsSize - 1); // Used to plan memory int size = numsSize; //
Allocate memory returnSize Pointer to constant So no malloc // retNums Store the last returned result int ** retNums = (int **)
malloc(sizeof(int *) * size); // returnColumnSizes storage retNums Size of each column *
returnColumnSizes= (int *)malloc(sizeof(int *) * size); for(int i = 0; i <
numsSize; i++){ // Judge whether the current benchmark value has been calculated before If so, proceed directly to the next cycle if(i > 0 && nums[i] == nums[i-
1]) continue; // The sum of three is equal to 0 There must be a negative number So when the reference value is greater than 0 There's no need to continue after the if(nums[i] > 0) break; int
left= i + 1; int right = numsSize - 1; while(left < right){ int sum = nums[i] +
nums[left] + nums[right]; if(sum == 0){ // Two here while Circulation is also for weight removal while(left < right
&& nums[left] == nums[left + 1]){ left++; continue; } while(left < right && nums
[right] == nums[right - 1]){ right--; continue; } // Store three numbers in the array retNums[*
returnSize] = (int *)malloc(sizeof(int) * 3); // Because it's the sum of three So two-dimensional array retNums Every column is 3
I think it's OK to use one-dimensional storage Two dimensional chicken ribs Is it used to improve the difficulty ? (*returnColumnSizes)[*returnSize] = 3; retNums[*
returnSize][0] = nums[i]; retNums[*returnSize][1] = nums[left++]; retNums[*
returnSize][2] = nums[right--]; *returnSize += 1; // Soul code Reschedule the memory size to the original size 2 times if(*
returnSize>= size){ size = size * 2; retNums = (int **)realloc(retNums, sizeof(
int *)*size); *returnColumnSizes = (int *)realloc(*returnColumnSizes, sizeof(int
*) * size); } }else if(sum > 0) // If the sum of the three is greater than 0 It means that the positive number is too large Then you have to right-- right--; else
// less than 0 It means that the negative number is too small That's it left++ left++; } } return retNums; }

By the way ： I always thought returnColumnSizes Is the array to return , Until after several submissions , Only to find out that things are wrong , embarrassed

realloc It's still very useful , Probably saved 10MB Space of , Quick sort can be done without writing it yourself , Direct call qsort That's it , use qsort I did it again , It's the same as the quick schedule I wrote myself , Looks like I'm doing a good job

Technology
Daily Recommendation
views 2