一、C语言实现
/** * 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 cmp(const void *a, const void *b){ return *((int *)a) - *((int *)b);}int **fourSum(int *nums, int numsSize, int target, int *returnSize, int **returnColumnSizes){ if (numsSize < 4) { *returnSize = 0; *returnColumnSizes = NULL; return NULL; } // 先对数组进行排序 qsort(nums, numsSize, sizeof(int), cmp); // 初始化*returnSize *returnSize = 0; // 调配存储四元组的数组 int **returnArr = (int **)malloc(sizeof(int *) * (numsSize - 2) * (numsSize - 2)); *returnColumnSizes = (int *)malloc(sizeof(int) * (numsSize - 2) * (numsSize - 2)); // 开始进入循环 // 因为进行了剪枝操作，因而，要用i < numsSize - 3作为终止循环的条件 // 否则会导致数组拜访越界 for (int i = 0; i < numsSize - 3; i++) { // 剪枝操作 if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) { break; } if (nums[i] + nums[numsSize - 3] + nums[numsSize - 2] + nums[numsSize - 1] < target) { continue; } // 首元素去重 if (i > 0 && nums[i] == nums[i - 1]) { continue; } // 因为进行了剪枝操作，因而，要用j < numsSize - 2作为终止循环的条件 // 否则会导致数组拜访越界 for (int j = i + 1; j < numsSize - 2; j++) { // 剪枝操作 if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) { break; } if (nums[i] + nums[j] + nums[numsSize - 2] + nums[numsSize - 1] < target) { continue; } // 第二个元素去重 if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } int head = j + 1; int tail = numsSize - 1; while (head < tail) { // 左指针去重 if (head > j + 1 && nums[head] == nums[head - 1]) { head++; continue; } // 右指针去重 if (tail < numsSize - 1 && nums[tail] == nums[tail + 1]) { tail--; continue; } if (nums[i] + nums[j] + nums[head] + nums[tail] == target) { returnArr[*returnSize] = (int *)malloc(sizeof(int) * 4); returnArr[*returnSize][0] = nums[i]; returnArr[*returnSize][1] = nums[j]; returnArr[*returnSize][2] = nums[head]; returnArr[*returnSize][3] = nums[tail]; (*returnColumnSizes)[*returnSize] = 4; (*returnSize) += 1; head++; tail--; } else if (nums[i] + nums[j] + nums[head] + nums[tail] > target) { tail--; } else { head++; } } } } return returnArr;}二、JS实现
/** * @param {number[]} nums * @param {number} target * @return {number[][]} */const fourSum = function (nums, target) { const len = nums.length if (len < 4) { return [] } nums.sort((x, y) => { return x - y }) const results = [] for (let i = 0; i < len; i++) { if (i > 0 && nums[i - 1] === nums[i]) { continue } // 剪枝操作 if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) { break } // 剪枝操作 if (nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) { continue } for (let j = i + 1; j < len; j++) { if (j > i + 1 && nums[j - 1] === nums[j]) { continue } // 剪枝操作 if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) { break } // 剪枝操作 if (nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) { continue } let head = j + 1 let tail = len - 1 while (head < tail) { if (head > j + 1 && nums[head - 1] === nums[head]) { head++ continue } if (tail < len - 1 && nums[tail + 1] === nums[tail]) { tail-- continue } if (nums[i] + nums[j] + nums[head] + nums[tail] === target) { // 存储符合条件的四元组到后果数组 results.push([nums[i], nums[j], nums[head], nums[tail]]) // 将头指针右移，尾指针左移 head++ tail-- } else if (nums[i] + nums[j] + nums[head] + nums[tail] > target) { tail-- } else { head++ } } } } return results}- 工夫复杂度：O(n^3)，其中n是数组的长度。排序的工夫复杂度是O(nlogn)，枚举四元组的工夫复杂度是 O(n^3)，因而总工夫复杂度为 O(n^3+nlogn)==O(n^3)。
- 空间复杂度：O(logn)，其中n是数组的长度。空间复杂度次要取决于排序额定应用的空间。此外排序批改了输出数组nums，理论状况中不肯定容许，因而也能够看成应用了一个额定的数组存储了数组nums 的正本并排序，空间复杂度为 O(n)。