2.10python如何从数组中找出满足 a+b=c+d的两个数对

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2.10python如何从数组中找出满足 a+b=c+d的两个数对，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1540字，纯文字阅读大概需要3分钟。

内容图文

题目描述：

给定一个数组，找出数组中是否有两个数对(a，b)和(c，d)，使得 a+b=c+d，其中 a、b、c 和 d 是不同的元素。如果有多个答案，打印任意一个即可。例如给定数组 [3，4，7，10，20，9，8]，可以找到两个数对(3,8)和(4,7)，使得 3+8=4+7.

思路：

最简单的方法是四重遍历，对所有可能的数对，判断是否满足要求，若是则打印出来，此方法的时间复杂度为O(n**4)；
现介绍字典法：以数对为单位进行遍历，在遍历过程中，把数对和数对的值存在字典中(键为数对的和，值为数对)，当遍历到一个键值对时，如果它的和在字典中已经存在，那么就找到了满足条件的键值对。

算法性能分析：
时间复杂度为O(n**2)，因为使用了双重循环，而字典的插入与查找操作实际的时间复杂度为O(1)；

代码实现：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time    : 2020/1/22 19:31
# @Author  : buu
# @Software: PyCharm
# @Blog    ：https://blog.csdn.net/weixin_44321080
class Pair:
    def __init__(self, first, second):
        self.first = first
        self.second = second


def findPairs(arr):
    sumPair = dict()  # 键为数对的和，值为数对
    n = len(arr)
    i = 0
    while i < n:  # 遍历数组中所有可能的数对
        j = i + 1
        while j < n:
            sums = arr[i] + arr[j]
            if sums not in sumPair.keys():  # 若数对的和在字典的键中不存在，在加入
                sumPair[sums] = Pair(arr[i], arr[j])
            else:  # 若数对的和存在字典的键中，则满足要求，打印出来即可
                p = sumPair[sums]
                print('(' + str(p.first) + ',' + str(p.second)                       + ')', '(' + str(arr[i]) + ',' + str(arr[j]) + ')')
                return True
            j += 1
        i += 1
    return False


if __name__ == '__main__':
    arr = [3, 4, 7, 10, 20, 9, 8]
    findPairs(arr)

结果：

end

• 点赞
• 收藏
• 分享
• • 文章举报

内容总结

以上是互联网集市为您收集整理的2.10python如何从数组中找出满足 a+b=c+d的两个数对全部内容，希望文章能够帮你解决2.10python如何从数组中找出满足 a+b=c+d的两个数对所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端