版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | http://vearne.cc

问题描述

在一个有序整型数组中,从其中任意挑2个数(不重复)相加等于目标值target
求所有这样的组合
比如有以下数组

case1:

target=6

[1, 2, 3, 4, 5, 7, 9]

返回结果为

[(1,5), (2,4)]

case2:

target=6

[1, 7, 9]

返回结果为

[]

case3:

target=9

[1, 2, 3, 4, 5, 7, 9]

返回结果为

[(2,7)]

解题思路

对这个问题,我们可以这样思考,以case1 为例
如果对于1, 可以从右向左找,可以找到5,与1相加可以等于目标值6
这时候再看2有没有合适的值能够与之相加等于目标值的时候,我们只需要找
[3, 4]就可以了,这是因为左边的数增大了,右边已经查找过的数,显然已经太大
方案
1)设2个指针分别指向数组的最左和最右
2) 移动右边的指针直到无法找到合适的值或者已经找到合适的值
3)移动左边的指针
4)持续步骤2和3,直到左右2个指针重合

时间复杂度为O(n)
完整代码:

def find(array, target):
    i = 0
    j = len(array) - 1
    res = []
    while i < j:
        while i < j and array[j] > (target - array[i]):
            j -= 1

        if (array[i] + array[j]) == target and i != j:
            res.append((i, j))

        i += 1

    return res

def main():
    a = [1,2,3,4,5,7]
    print find(a, 6)
    a = [1,7,9]
    print find(a, 6)
    a = [1, 2, 3, 5, 7, 9]
    print find(a, 9)

if __name__ == "__main__":
    main()

如果我的文章对你有帮助,你可以给我打赏以促使我拿出更多的时间和精力来分享我的经验和思考总结。

微信支付码

发表评论

电子邮件地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据