python使用双指针算法进阶,解决数组求和问题

2024-01-08 14:29:38

对给定的数组的求和问题中,之前求了数组中三个数的和的问题的一篇问题,在此文章中主要描述的是使用双指针的方式来进行求解,有空的可以查看一下前一篇文章中的解决问题的思路。

这次主要是想要解决给定数组中,求解四个数的和的问题,给定一个包含有n个整数的数组和给定一个目标总值,对这个数组任意取4个元素,使这四个数的和与给定的目标总值相等,并且找到的四个数组成的元组要不重复。

例如给定数组,A=[1,0,-1,0,-2,2],给定的目标总值是0,求满足条件的集合。

添加图片注释,不超过 140 字(可选)

添加图片注释,不超过 140 字(可选)

添加图片注释,不超过 140 字(可选)

针对给定条件,之前的限制条件是三个数,所以可以固定一个数来进行左右指针的查找,而这次解决问题的思路同样可以使用双指针来进行解决,只是由于这次的限制条件变成了四个数,所以需要再外层再多嵌套一层循环来实现。

这里同样是固定数,但是与三个数相比需要多固定一个数,也就是固定两个数的方式,然后双指针从左右两个方向来进行遍历查找,直到知道四个数的和为给定的目标值。

在循环的内部同样是采用将元素去重的方式来减少不必要的计算,这里需要注意的是这里给定的数据可能是正数也可能是负数,所以不用判断数据大于0并且终止循环。如下是python代码实现:

def fourSum(self, array,sum_):
    array.sort()
    res=[]
    length=len(array)
    for i in range(length-3):#双层循环
        if i!=0 and array[i]==array[i-1]:
            continue
        for j in range(i+1,length-2):
            if j!=i+1 and array[j]==array[j-1]:continue
            l=j+1
            r=length-1
            while(l<r):
                s=array[i]+array[j]+array[l]+array[r]
                if(s==sum_ and [array[i],array[j],array[l],array[r]] not in res):
                    res.append([array[i],array[j],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
                elif(s>sum_):
                    r-=1
                else:
                    l+=1
    return res

文章来源:https://blog.csdn.net/Mrsawyer/article/details/135454806
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。