Fork me on GitHub

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://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()

请我喝瓶饮料

微信支付码

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注