抛砖引玉

在编程中，我们常常会用到循环去不断地地处理数据。这个时候我们可以有很多方法去将减少循环次数，去缩小待处理的数据的范围，比如二分查找就是我们常用的一种思想。

但是如果我们需要多层循环去处理数据，而且有时候还会重复处理某个数据呢？这显然是低效且不必要的。双指针思想就是为了处理这种情况，可以有效地减少某些数据的重复处理。

先通过一个简单的例子来打个基调，这题是我对力扣第一题两数之和的魔改版，方便演示：

题目描述：

给定一个有序数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,3], target = 6
输出：[0,1]

没有什么算法基础的伙伴可能看到这道题想的就是直接来个双重循环，这种简单粗暴的思路的伪代码大概长这样：

len = nums.length   // 获取数组的长度

for (i = 0; i < len; i++) {
  for (j = i + 1; j < len; j++) {
    val = nums[i] + nums[j]
    if (val === target) {
      return [i, j]
    }
  }
}

我们来简单算一下这个方法的时间复杂度，最外层的 for 循环体中的语句要被执行len 次，而在每次外层循环执行的时候，内层循环要执行len - i - 1 次。也就是说最坏情况下要执行 len * (len - i - 1) 次，时间复杂度达到了 O(n^2)

这在算法领域是一个非常高的时间复杂度了。那有没有什么改进方法呢？

由于是个有序数组，其实我们知道这个数组满足条件的值域的。当目标元素在数组的末端，也就是len - 1 和 len - 2时，是值域的最大值。同理，当目标元素在数组头部时，也就是0和1时，是值域的最小值。

那我们是否就可以定两个点，一个在值最小的端点，一个在值最大的端点。这样可以有效地控制我们两个元素和的大小。如果元素和大于目标值，我们让大端点向小端点的方向逐点移动。如果元素和小于目标值，我们让小端点向大端点的方向逐点移动。

function sum(nums, target) {
  const len = nums.length
  let left = 0,
      right = len - 1
  
  // 因为题目要求同一个答案不能在元素里重复出现，所以不能出现 left 和 right 重合的情况
  while (left < right) {
    const val = nums[left] + nums[right]
    if (val === target) {
      return [left, right]
    } else if (val < target) {
            left ++
    } else {
      right --
    }
  }
}

我们来看看这个方法的性能。首先它产生的内存空间是常数个，所以空间复杂度是O(1)。其次，我们算法在最坏的情况下无非是一个端点一直移动到另一个端点，执行次数是 len - 1 次，所以时间复杂度是 O(n)。

性能提升是及其显著的！当然这题我们仔细观察的话，其实还有可以优化的地方。我们可以从示例中看到，元素是存在相同的情况，比如[3, 3]。我们可以让端点移动的时候，碰到有序的元素直接跳过，无需再进行重复计算、判断。

function sum(nums, target) {
   const len = nums.length
   let left = 0,
       right = len - 1

   // 因为题目要求同一个答案不能在元素里重复出现，所以不能出现 left 和 right 重合的情况
   while (left < right) {
     const val = nums[left] + nums[right]
     if (val === target) {
       return [left, right]
     } else if (val < target) {
       left ++
       // 当然，由题意我们可以知道数组中必定有答案，其实 left < right 这个判别是可以不用写的，它不可能再没找到答案之前一直都是连续相等的
       while (nums[left] === nums[left - 1] && left < right) {
         left ++
       }
     } else {
       right --
       while (nums[right] === nums[right + 1] && left < right)
     }
   }
}

想必看到这里，应该能够较为形象地理解双指针，其实就是在循环时定义两个或多个标记，从而通过条件不断地去改变答案区间搜索答案。上面这个例子就是双指针中经典代表 —— 对撞指针。

牛刀小试 —— 对撞指针

对撞指针其实可以类比成小学数学中的相遇问题，两个标记不断地根据条件向对方移动，标记间形成答案区间，而这个区间是不断缩小的，直到找到答案为止。

我们来看一道经典题来感受一下对撞指针 —— LC15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

这题如果我们直接遍历每一种可能的话，会发现是非常复杂的，我们有可能回获得许多重复的元素，而且还需要单独维护一个空间去判断符合条件的组合是否已经出现过。这样的话，我们空间和时间的开销是非常大的。

这题我们仔细观察可以发现，题要的是值的组合，而不是满足条件的下标的组合，所以我们问题可以简化许多，可以将问题从无序层面拉到有序层面进行思考。

nums.sort((a, b) => a - b)

我们继续思考，如何去简化我们的问题， 找到在能够支持我们不断迭代的规律、性质，也就是所谓的循环不变量。

由于我们需要每次迭代查找3个元素，这使得我们要标记元素很多，不好控制，我们看看能不能将标记指针数量缩小到2个。

由于已经对数组有序，我们其实可以在遍历的时候对每个元素进行操作，在每个元素的右侧进行对撞指针处理，这样可以很好地控制指针的移动，而且在讲指针简化到2个的同时又不会有任何遗漏。我们来具体看一下代码深入理解一下：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const len = nums.length
    // 特殊判别一下，如果数组长度不到 3 的话，直接返回空数组
    if (len < 3) return []
      // 对数组进行从小到大排序
    nums.sort((a, b) => a - b)
    // 结果数组
    let ans = []

    for (let i = 0; i < len - 2; i++) {
          // 如果遍历的元素，前后一样的话直接跳过此次处理，这样可以避免答案元素重复的情况
        if (nums[i] === nums[i - 1]) {
            continue
        }
        let left = i + 1,
            right = len - 1
        
        while (left < right) {
            const val = nums[i] + nums[left] + nums[right]
            if (val === 0) {
                ans.push([nums[i], nums[left], nums[right]])
                left ++
                right --
                  // 如果左右指针移动后的元素的值与移动前一致，可以直接继续移动，这样可以避免重复
                while (nums[left] === nums[left - 1]) {
                    left ++
                } 
                while (nums[right] === nums[right + 1]) {
                    right --
                }
            } else if (val > 0) {
                right --
                while (nums[right] === nums[right + 1]) {
                    right --
                }
            } else {
                left ++
                while (nums[left] === nums[left - 1]) {
                    left ++
                }
            }
        }
    }

    return ans
};

最后我们来看看我们这种写法的复杂度。首先引入的空间都是常数级的，所以空间复杂度是O(1)。时间复杂度上，我们遍历每个元素是O(n)，双指针操遍历O(n)，每个语言的排序算法可能不太一样，但是绝对不会超过O(n^2)（要知道，冒泡排序这种较慢的排序都才O(n^2)，语言的排序 API 时间复杂度肯定是要比这个低的）。所以最后的时间复杂度是 O(n^2)

熟能生巧

我们这次通过一道非常经典的算法题来巩固我们对双指针的理解，做到真正地吃透本质。题是永远做不完的，我们需要将题目做精做透，这样才能真正地解决问题，而不是靠题海解决题。

LC11. 盛最多水的容器

这题有一个地方其实是帮我们降低了难度，容器的容量只跟容器两端的高度有关，容器里的垂线高度对我们容器的容量不会产生任何影响，说白了就是提示你往双指针去思考。

我们这题还是采用对撞指针的思想，尽管我们垂线的高度不是单调变换的，但是我们可以简单证明一下对撞指针的可行性。

首先我们知道，容器的容量由两个因素决定：两端较短垂线的高度 和 两端之间的距离， 即：

容量 = Math.min(height[left], height[right]) * (right - left)

现在我们只需确定按照什么条件去移动指针使得这个方法可行。

我们在每次移动时，移动高度值小的指针，因为我们要使得 容量 最大，那么根据上面的公式，我们发现是一个right - left是一个不断递减的值，我们要想遇到最大值，我们就需要保证Math.min(height[left], height[right])这个部分越大越好。

所以我们每次移动的指针都是高度值最小的那一个。上代码辅助理解一下吧：

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let ans = 0
    const len = height.length

    let left = 0,
        right = len - 1
    
    while (left < right) {
        if (height[right] > height[left]) {
            const val = height[left] * (right - left)
            ans = Math.max(ans, val)
            left ++
        } else {
            const val = height[right] * (right - left)
            ans = Math.max(ans, val)
            right --
        }
    }

    return ans
};

时间复杂度当然就是双指针遍历的复杂度啦，O(n)。空间复杂是O(1)。