C语言 | Leetcode C语言题解之第15题三数之和

题目：

题解：

int cmp(const void *x, const void *y)
{
    return *(int*)x - *(int*)y;
}
//判断重复的三元组
bool TheSame(int a, int b, int c, int **ans, int returnSize)
{
    bool ret = true;
    for(int i = 0;i < returnSize;++i)
    {
        if(a == ans[i][0] && b == ans[i][1] && c == ans[i][2])
        {
            ret = false;
            break;
        }
    }
    return ret;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    //给nums排序，以便去除重复元素,时间O(nlogn)到O(n2)之间
    qsort(nums, numsSize, sizeof(int), cmp);
    //最多可能的三元组数
    // double maxRoom = 1;
    //ans行大小初始化
    *returnSize = 0;
    //特判
    if(numsSize < 3) return NULL;
    //计算maxRoom,用组合的思想
    // maxRoom = (numsSize) * (numsSize - 1) * (numsSize - 2);
    // maxRoom /= 6;
    //分配返回数组内存
    int **ans = (int**)calloc(20000, sizeof(int*));
    //取一个元素为中间元素，不能取头尾，时间:O(n2)
    for(int i = 0, left = 1, right = numsSize - 1;i < numsSize - 2 && nums[i] <= 0;++i)
    {
        //初始化
        left = i + 1;
        right = numsSize - 1;
        //第一个数定下来之后，双指针法遍历第二和第三个数，时间:O(n)
        while(left < right)
        {
            if(nums[i] + nums[left] + nums[right] < 0)
            {
                ++left;
            }
            else if(nums[i] + nums[left] + nums[right] > 0)
            {
                --right;
            }
            else//符合条件的三元组找到了
            {
                //并且不重复
                if(TheSame(nums[i], nums[left], nums[right], ans, *returnSize))
                {
                    ans[(*returnSize)] = (int*)calloc(3, sizeof(int));
                    ans[(*returnSize)][0] = nums[i];
                    ans[(*returnSize)][1] = nums[left];
                    ans[(*returnSize)][2] = nums[right];
                    ++(*returnSize);
                }
                ++left;
                --right;
            }
        }
    }
    //申请数组列的内存
    *returnColumnSizes = (int*)calloc((*returnSize), sizeof(int));
    //内存赋值3
    for(int i = 0;i < *returnSize;++i)
    {
        (*returnColumnSizes)[i] = 3;
    }
    return ans;
}