TOP101题解 | BM54#三数之和#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.26
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 三重for循环可以解决但是太低效
 * @param num int整型一维数组 
 * @param numLen int num数组长度
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
#include <stdlib.h>
int compar(const void* p1, const void* p2)
{
    return (*(int*)p1 - *(int*)p2);
}

int** threeSum(int* num, int numLen, int* returnSize, int** returnColumnSizes ) 
{
    // write code here
    qsort(num, numLen, sizeof(num[0]),  compar);
    int** result = (int**)malloc(sizeof(int*) * numLen * numLen);
    *returnSize = 0;
    *returnColumnSizes = (int*)malloc(sizeof(int) * numLen * numLen);

    for(int i = 0; i < numLen; i++)
    {
        if(i > 0 && num[i] == num[i - 1])
        {
            continue;
        }

        int target = -num[i];
        int left = i + 1;
        int right = numLen - 1;

        while (left < right) 
        {
            int sum = num[left] + num[right];
            if (sum == target) 
            {
                result[*returnSize] = (int*)malloc(sizeof(int) * 3);
                result[*returnSize][0] = num[i];
                result[*returnSize][1] = num[left];
                result[*returnSize][2] = num[right];
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;
                
                while (left < right && num[left] == num[left + 1]) 
                {
                    left++; // Skip duplicates
                }
                while (left < right && num[right] == num[right - 1]) 
                {
                    right--; // Skip duplicates
                }
                left++;
                right--;
            } 
            else if (sum < target) 
            {
                left++;
            } 
            else 
            {
                right--;
            }
        }
    }
    
    return result;
}