对撞指针的学习——以LeetCode第15题为例

引言

在进行LeetCode题库作答过程中，遇到了多个双指针的问题，遂进行学习。

初步了解到，双指针方法为针对有序数组的遍历的一种方法，可分为快慢指针与对撞指针。

相比简单的遍历，双指针可更快的达到结果。

对撞指针原理

对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。

伪代码如下：

function 对撞指针 (list) {
  var left = 0;
  var right = list.length - 1;
  //遍历数组
  while (left <= right) {
    // 一些条件判断 和处理
    ... ...
    left++
    right--;
  }
} 

题目描述

给你一个包含 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]
输出：[]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/3sum

解题分析

笔者最初进行解题时，安排三个变量进行遍历，index1从0开始，index2从index1+1开始，index3从index2+1开始，算法并无任何问题，但所需时间长、所占内存大，在LeetCode题库内会出现“超出时间限制”的提示。

无奈，只好选择学习双指针，利用对撞指针减少所需时间及所占内存。

程序代码

解题所写代码如下，可优化空间很大，仅供参考。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        lens=len(nums)
        #长度小于3，不考虑
        if lens<3:
            return []
        #对数组进行排序
        nums.sort()
        #若排序后最大值小于0/最小值大于0，不考虑
        if nums[lens-1]<0 or nums[0]>0:
            return []

        result=[]
        #使用对撞指针，i为变化的,left与right分别为左右对撞指针
        for i in range(lens):
            left=i+1
            right=lens-1
            #对撞指针的规则，left大于等于right时发生碰撞
            while left<right:
                #如果满足条件，则存储,并收缩指针
                if nums[i]+nums[left]+nums[right]==0:
                    temlist=[nums[i],nums[right],nums[left]]
                    temlist.sort()
                    left+=1
                    right-=1
                    if temlist not in result:
                        result.append(temlist)
                #不满足条件
                #三数之和大于0，减小right
                elif nums[i]+nums[left]+nums[right]>0:
                    right-=1
                #三数之和小于0，增大left
                else:
                    left+=1
            
        return result