电子网站建设推广方案,济南网站建设内容设计,福建建筑人才网官网,网站推广的基本方法是什么对于双指针算法#xff0c;一般是用于解决对数组等数据结构进行遍历的问题的一种编程思路#xff0c;其主要是使用两个指针共同配合工作#xff0c;对数组等数据结构进行搜索并返回得到想要搜索的结果#xff0c;针对给定问题#xff0c;三数之和问题#xff0c;这是一个…对于双指针算法一般是用于解决对数组等数据结构进行遍历的问题的一种编程思路其主要是使用两个指针共同配合工作对数组等数据结构进行搜索并返回得到想要搜索的结果针对给定问题三数之和问题这是一个双指针算法中的经典问题而且使用的是双指针算法中的一个类型也就是左右双指针算法这个问题主要是以三个数为限制条件对左右两个指针进行调整。如下如问题的描述
给定包含有n个整数的数组对这个数组中的元素进行判断是否存在有三个元素可以使得这三个元素的和为0需要得到的是一个列表列表元素是符合条件的三个数的元组并且这个列表中不存在重复元素。 添加图片注释不超过 140 字可选
对于这个问题的求解大部分人直接使用暴力求解也是可以快速得到问题的解的这里大致说一下暴力求解的问思路可以使用三个循环和一个判断就可以三个循环进行嵌套对给定数组直接进行遍历每一层循环代表的是对列表查找组成元组的三个元素最后一个判断就是判断三个数的和为0并且与最终结果列表中的元素不重复以下是使用python暴力求解的代码
def threeSum(self, array):array.sort()lengthlen(array)res[]for i in range(length):#三层循环for j in range (i1,length):for k in range(j1,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: breakif k 0 and array[k] array[k - 1]: continue l, r k 1, len(array) - 1while l r:s array[k] array[l] array[r]if s 0:l 1while l r and array[l] array[l - 1]: l 1#进行元素去重elif s 0:r - 1while l r and array[r] array[r 1]: r - 1else:res.append([array[k], array[l], array[r]])l 1r - 1while l r and array[l] array[l - 1]: l 1while l r and array[r] array[r 1]: r - 1return res
