关于c:16-最接近是三数之和

一、双指针法——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)。