我们经常会用两个指针来处理一些问题，这里对套路做简单的总结。
模版：
注意，双指针使用的条件：因为核心是缩小求解范围（l 和 r 之间的范围），所以数组必须满足一定的规律，才行：比如 15 和 881 都是有序数组才行。

  1. function test(nums) {
  2.     let n = nums;
  4.     let l = 0;
  5.     let r = n - 1;
  6.     while (l < r) { // l r 指向未比较的地方
  7.         if ('condition1') {
  8.             // 两边同时缩
  9.             r--;
  10.             l++;
  11.         } else if ('condition2') {
  12.             r--; // 只右边缩
  13.         } else if ('condition3') {
  14.             l++; // 只左边缩
  15.         }
  16.     }
  17. }

15. 三数之和

https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/

直接暴力方法是 三层 for 循环：
1）第一层 for 循环，先固定一个数，
2）之后就是两数之和的问题，这里有 两层 for 循环

另外的还有巧妙的方法：如果对于原数组不加任何处理，那么很难有提高，我们需要利用有序数组，在计算累加和的优势。
对于 一个 升序数组，如果数组元素 已经大于 目标和 了，就没有必要向后递归判断了。

  1. // 模式识别：题目中有不重复 -> 数组排序 和 按照一定模式去做
  2. // 如何缩小查找范围
  3. var threeSum = function(nums) {
  4.     let n = nums.length;
  6.     if (n <= 2) {
  7.         return [];
  8.     }
  10.     let result = [];
  12.     // nums = nums.sort(); // 默认升序 -- 这个排序有问题
  13.     nums = nums.sort((a, b) => a - b);
  15.     let l;
  16.     let r;
  17.     for (let i = 0; i < n; i++) {
  18.         let num = nums[i];
  19.         if (num > 0) {
  20.             break;
  21.         }
  22.         if (i > 0 && nums[i] === nums[i - 1]) { // 去重：理解困难一些
  23.             continue;
  24.         }
  26.         l = i + 1;
  27.         r = n - 1;
  29.         // 据说是经典双指针操作：
  30.         while (l < r) { // l r 指向未比较的地方
  31.             let sum = num + nums[l] + nums[r];
  32.             if (sum === 0) {
  33.                 result.push([num, nums[l], nums[r]]);
  34.                 while(nums[r] === nums[r - 1]) { // 减到最后一个相同
  35.                     r--;
  36.                 }
  37.                 while(nums[l] === nums[l + 1]) { // 加到最后一个相同
  38.                     l++;
  39.                 }
  40.                 r--;
  41.                 l++;
  42.             } else if (sum > 0) {
  43.                 r--;
  44.             } else {
  45.                 l++;
  46.             }
  47.         }
  48.     }
  50.     return result;
  51. }

349. 两个数组的交集

特别有创意！

  1. var intersection = function(nums1, nums2) {
  2.     let n1 = nums1.length;
  3.     let n2 = nums2.length;
  5.     nums1.sort((a, b) => a - b);
  6.     nums2.sort((a, b) => a - b);
  8.     let i1 = 0;
  9.     let i2 = 0;
  10.     let ans = [];
  12.     while (i1 < n1 && i2 < n2) { // 很经典的双指针
  13.         let num1 = nums1[i1];
  14.         let num2 = nums2[i2];
  16.         if (num1 === num2) {
  17.             if ((ans.length === 0) || ans[ans.length - 1] !== num1) {
  18.                 ans.push(num1);
  19.             }
  20.             i1++;
  21.             i2++;
  22.         } else if (num1 < num2) {
  23.             i1++;
  24.         } else {
  25.             i2++
  26.         }
  27.     }
  29.     return ans;
  30. };

881. 救生艇

和 15 很像，但是很简单，操作的也只有两个元素，所以少一层for循环。

  1. var numRescueBoats = function(people, limit) {
  2.     let n = people.length;
  3.     people = people.sort((a, b) => a - b);
  4.     if (people[n - 1] > limit) {
  5.         return null; // 船的容量小于最重的人，这活干不了
  6.     }
  8.     let light = 0;
  9.     let heavy = n - 1;
  10.     let result = [];
  12.     while (light < heavy) {
  13.         if (people[light] + people[heavy] <= limit) {
  14.             result.push([people[light], people[heavy]]);
  15.             light++;
  16.             heavy--;
  17.         } else {
  18.             result.push([people[heavy]]);
  19.             heavy--;
  20.         }
  21.     }
  23.     return result.length;
  24. };

但是有问题，有这样一种case特别烦人：

  1. numRescueBoats([3,2,2,1], 3)

排序之后 是 [1, 2, 2, 3]
[3], [1,2]被取走之后，只剩下[2]，而此时 l 和 r 指向这同一个位置。
要把这个逻辑补上，得写一堆代码，但是有简单方法：（个人不喜欢）

  1. // 改为
  2. while (light <= heavy) {

11. 盛最多水的容器

这个乍一看和 “接雨水”问题很像，但是却可以使用 双指针去做，但是我还是不很了解，但是求解过程是熟悉。
看这个题解：https://leetcode.cn/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/

  1. var maxArea = function(height) {
  2.     let n = height.length;
  3.     let left = 0;
  4.     let right = n - 1;
  5.     let max = 0;
  7.     while (left < right) {
  8.         let area = (right - left) * Math.min(height[left], height[right]);
  9.         if (max < area) {
  10.             max = area;
  11.         }
  13.         if (height[left] < height[right]) {
  14.             left++;
  15.         } else {
  16.             right--;
  17.         }
  18.     }
  20.     return max;
  21. };