双指针算法，python求解给定数组的三数之和问题

对于双指针算法，一般是用于解决对数组等数据结构进行遍历的问题的一种编程思路，其主要是使用两个指针共同配合工作，对数组等数据结构进行搜索并返回得到想要搜索的结果，针对给定问题，三数之和问题，这是一个双指针算法中的经典问题，而且使用的是双指针算法中的一个类型，也就是左右双指针算法，这个问题主要是以三个数为限制条件，对左右两个指针进行调整。如下如问题的描述：

给定包含有n个整数的数组，对这个数组中的元素进行判断，是否存在有三个元素，可以使得这三个元素的和为0，需要得到的是一个列表，列表元素是符合条件的三个数的元组，并且这个列表中不存在重复元素。

添加图片注释，不超过 140 字（可选）

对于这个问题的求解，大部分人直接使用暴力求解，也是可以快速得到问题的解的，这里大致说一下暴力求解的问思路，可以使用三个循环和一个判断就可以，三个循环进行嵌套，对给定数组直接进行遍历，每一层循环代表的是对列表查找组成元组的三个元素，最后一个判断就是判断三个数的和为0并且与最终结果列表中的元素不重复，以下是使用python暴力求解的代码：

def threeSum(self, array):
    array.sort()
    length=len(array)
    res=[]
    for i in range(length):#三层循环
        for j in range (i+1,length):
            for k in range(j+1,length):
                if array[i]+array[k]+array[j]==0 and not [array[i],array[j],array[k]] in res:
                    res.append([array[i],array[j],array[k]])
    return res

对于暴力求解，其在给定数组的元素较少的情况下，还可以采用，但是在数据量增大的情况，时间复杂度本身就很高，将会大大的降低效率，不适合使用。

添加图片注释，不超过 140 字（可选）

而在使用左右双指针算法的方法中，其思路是对于三数之和为零，其实是可以看做前两个数的和等于最后一个数的负数（问题条件中给定的数据都是正整数），在求和之前可以先将数组直接进行排序，这样就可以降低复杂度，避免了每一次的遍历，在已经进行了排序的前提下，对数组只遍历一遍，将每一个遍历过的元素都当做最后一个负数的元素，然后在遍历过程中使用左右双指针来分别指向当前元素的下一个元素以及数组的最后一个元素。在指针移动过程中，只要左指针小于右指针，则就计算三数之和来决定左右指针是否应该移动，而且在移动的过程中就可以判断是否是重复元素，如果是重复元素，跳过即可。

添加图片注释，不超过 140 字（可选）

如下是使用左右双指针算法求解三数之和的代码：

def threeSum(self, array):
    array.sort()
    res= []
    for k in range(len(array) - 2):
        if array[k] > 0: break
        if k > 0 and array[k] == array[k - 1]: continue 
        l, r= k + 1, len(array) - 1
        while l < r:
            s = array[k] + array[l] + array[r]
            if s < 0:
                l += 1
                while l < r and array[l] == array[l - 1]: l += 1#进行元素去重
            elif s > 0:
                r -= 1
                while l < r and array[r] == array[r + 1]: r -= 1
            else:
                res.append([array[k], array[l], array[r]])
                l += 1
                r -= 1
                while l < r and array[l] == array[l - 1]: l += 1
                while l < r and array[r] == array[r + 1]: r -= 1
    return res