前置知识

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。
换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

例题

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 :::info 示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。 ::: 提示：
3 <= nums.length <= 10^3<br />-10^3 <= nums[i] <= 10^3<br />-10^4 <= target <= 10^4

思路

我们可以向将目标数组升序，然后采用双指针方法解决。
首先，从左往右遍历元素，确定一个基础点_i_(0 <= i < nums.length-2)，然后根据该基准点的右侧用双指针去寻找最小的差值。
当基础点为_i_时，双指针初始指向位置分别为：

  • left: i + 1;
  • right: nums.length - 1;

此时计算 i、left、right所指元素的和sum，然后计算出与目标值target的差值diff。如果差值
diff比记录中的最小值min要小，则更新最小值和结果res；然后再比较当前元素和sum与目标值的大小。

  • 当sum < target， 则左指针向右移动，
  • 当sum > target，则右指针向左移动，
  • 当sum = target，则直接返回sum.
    1. var threeSumClosest = function(nums, target) {
    2.   // 升序排序
    3.   nums.sort((a, b) => a - b) 
    4.   let min = Infinity
    5.   let res = 0;
    6.   const len = nums.length
    7.   for (let i = 0; i < len - 2; i++) {
    8.       let [left, right] = [i + 1, len - 1]
    9.       // 遍历位置i后的元素
    10.       while (left < right) {
    11.           let sum = nums[i] + nums[left] + nums[right];
    12.           let diff = Math.abs(sum - target);
    13.           // 如果当前元素更小，更新最小值
    14.           if (diff < min) {
    15.               min = diff;
    16.               res = sum;
    17.           }
    18.           // 如果当前元素和小于目标值，left+1使得sum增大；大于目标值则right-1
    19.           if (sum < target) {
    20.               left++
    21.           } else if (sum > target) {
    22.               right--
    23.           } else {
    24.               return sum
    25.           }
    26.       }
    27.   }
    28.   return res
    29. };

    167. 两数之和 II - 输入有序数组

    给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
    以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
    你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
    你所设计的解决方案必须只使用常量级的额外空间。 :::info 输入：numbers = [2,7,11,15], target = 9
    输出：[1,2]
    解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。 :::

    思路

    设置左右指针，分别指向数组第一个元素和最后一个元素，然后计算其总和。
    当总和sum小于目标值时，左指针向右移动；当总和sum大于目标值时，右指针向左移动，直到总和等于目标值时返回指针下标。
    1. var twoSum = function(numbers, target) {
    2.   const len = numbers.length;
    3.   let left = 0, right = len - 1;
    4.   while (left < right) {
    5.       let sum = numbers[left] + numbers[right];
    6.       if (sum < target) {
    7.           left++;
    8.       } else if (sum > target) {
    9.           right--;
    10.       } else {
    11.           return [left+1, right+1]
    12.       }
    13.   }
    14. };