算法题(7)

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

请我喝瓶饮料