一、双指针法——C语言实现
/** * 最靠近的三数和 * LeetCode第16题 * author: aliao language: C*/#include <stdio.h>#include <stdlib.h>int compare (const void *a, const void *b) { return (*(int *)a) - (*(int *)b);}int threeSumClosest(int *nums, int numsSize, int target){ // 先给数组升序排序 qsort(nums, numsSize, sizeof(int), compare); // 定义返回值 int best; for (int i = 0; i < numsSize; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int head = i + 1; int tail = numsSize - 1; while (head < tail) { // 求和 int sum = nums[i] + nums[head] + nums[tail]; // 将第一个三数之和存为最靠近解best if (i == 0 && head == 1 && tail == numsSize - 1) { best = sum; } // 更新三元素之和 if (abs(sum - target) < abs(best - target)) { best = sum; } if (sum < target) { // 左指针左移 head++; // 左指针去重 while (nums[head] == nums[head - 1]) { head++; } } else if (sum > target) { // 右指针左移 tail--; // 右指针去重 while (nums[tail] == nums[tail + 1]) { tail--; } } else { return target; } } } return best;}int main (void) { int nums[] = {-1, 2, 1, -4}; int numsSize = 4; int target = 1; printf("%d\n", threeSumClosest(nums, numsSize, target));}
二、双指针法——js实现
/** * @param {number[]} nums * @param {number} target * @return {number} */const threeSumClosest = function (nums, target) { const len = nums.length nums.sort((a, b) => { return a - b }) let best = Infinity for (let i = 0; i < len; i++) { // 去除首层循环反复的元素 if (i > 0 && nums[i] === nums[i - 1]) { continue } let tail = len - 1 let head = i + 1 while (head < tail) { // 求和 const sum = nums[i] + nums[head] + nums[tail] // 更新三元素之和 if (Math.abs(sum - target) < Math.abs(best - target)) { best = sum } if (sum > target) { // 右指针左移1 tail-- // 左指针去重 while (nums[tail] === nums[tail + 1]) { tail-- } } else if (sum < target) { // 左指针右移 head++ // 右指针去重 while (nums[head] === nums[head - 1]) { head++ } } else { // sum与target相等时，间接返回target return target } } } return best}console.log(threeSumClosest([-1, 2, 1, -4], 1))
- 工夫复杂度：O(n^2)，其中n是数组nums 的长度。咱们首先须要O(nlogn)的工夫对数组进行排序，随后在枚举的过程中，应用一重循环O(n)枚举a，双指针O(n)枚举b和c，故一共是O(n^2)。
- 空间复杂度：O(logn)。排序须要应用O(logn)的空间。然而咱们批改了输出的数组nums，在理论状况下不肯定容许，因而最坏状况就是应用了一个额定的数组存储了nums的正本并进行排序，此时应用数组的空间复杂度为O(n)。排序空间复杂度为O(logn)，额定的新数组空间复杂度是O(n)，因而综合起来就是O(logn)。