Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C - 15. 3Sum

---

參考資訊：
https://algo.monster/liteproblems/15
https://www.cnblogs.com/grandyang/p/4481576.html

題目：


解答：

int mysort(const void *a, const void *b)
{
    return (*(int *)a) - (*(int *)b);
}

/**
 * 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().
 */
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
    #define MAX_SIZE 30000

    int i = 0;
    int **ret = calloc(sizeof(int *), MAX_SIZE);

    *returnSize = 0;
    *returnColumnSizes = calloc(sizeof(int), MAX_SIZE);

    qsort(nums, numsSize, sizeof(int), mysort);
    for (i = 0; i < numsSize; i++) {
        int l = i + 1;
        int r = numsSize - 1;
        int chk = 0 - nums[i];

        if (nums[i] > 0) {
            break;
        }

        if ((i > 0) && (nums[i] == nums[i - 1])) {
            continue;
        }

        while (l < r) {
            if ((nums[l] + nums[r]) == chk) {
                int pos = (*returnSize)++;

                ret[pos] = calloc(sizeof(int), 3);
                ret[pos][0] = nums[i];
                ret[pos][1] = nums[l];
                ret[pos][2] = nums[r];
                (*returnColumnSizes)[pos] = 3;

                while ((l < r) && (nums[l] == nums[l + 1])) {
                    l += 1;
                }
                while ((l < r) && (nums[r] == nums[r - 1])) {
                    r -= 1;
                }
                l += 1;
                r -= 1;
            }
            else if (nums[l] + nums[r] < chk) {
                l += 1;
            }
            else {
                r -= 1;
            }
        }
    }

    return ret;
}