[幂演绎法 - 三个数的和] - 问题解决

快排 + 双指针法

代码

/**
 * 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 0
    if(numsSize < 3)
        return NULL; // If the input array has less than 3 elements, return NULL as no triplet can be formed

    qsort(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 sizes
    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;

    // Use three pointers to traverse the sorted array and find triplets that sum up to zero
    for (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 triplets
        while (indexMiddle < indexRight)
        {
            sum = nums[indexLeft] + nums[indexMiddle] + nums[indexRight];
            if (sum == 0)
            {
                // If the sum is zero, store the triplet in the ans array
                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;

                // 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 pointer
                indexRight--;
            }
            else
            {
                // If the sum is less than zero, increment the middle pointer
                indexMiddle++;
            }
        }
    }
    return ans; // Return the 2D array containing the unique triplets
}