Steward

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

程式語言 - LeetCode - C - 18. 4Sum

---

參考資訊：
https://algo.monster/liteproblems/18

題目：


解答：

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

    int i = 0;
    int j = 0;
    int l = 0;
    int r = 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 - 3; i++) {
        if ((i > 0) && (nums[i] == nums[i - 1])) {
            continue;
        }

        for (j = i + 1; j < numsSize - 2; j++) {
            if ((j > i + 1) && (nums[j] == nums[j - 1])) {
                continue;
            }

            l = j + 1;
            r = numsSize - 1;

            while (l < r) {
                long long sum = (long)nums[i] + nums[j] + nums[l] + nums[r];

                if (sum == target) {
                    int pos = (*returnSize)++;

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

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

    return ret;
}