组合和为N的数量-第13届蓝桥杯选拔赛Python真题精选

[导读]：超平老师的Scratch蓝桥杯真题解读系列在推出之后，受到了广大老师和家长的好评，非常感谢各位的认可和厚爱。作为回馈，超平老师计划推出《Python蓝桥杯真题解析100讲》，这是解读系列的第78讲。

组合和为N的数量，本题是2022年3月13日举办的第13届蓝桥杯青少组Python编程选拔赛真题编程部分第3题。题目要求将M个正整数中任意两个数进行组合，且求出每组组合的和， 请编程计算出M个正整数中有多少组组合的和恰好等于N。

先来看看题目的要求吧。

一.题目说明

编程实现：

给定一个正整数N和M个不同的正整数，然后将 M 个正整数中任意两个数进行组合，且求出每组组合的和， 问 M 个正整数中有多少组组合的和恰好等于N。

如：正整数N为6，M为5，5个不同的正整数分别为 1，2，3，4，5。

任意两数组合有10组：1 + 2，1 + 3，1 + 4，1 + 5，2 + 3，2 + 4，2 + 5，3 + 4，3 + 5，4 + 5, 其中和恰好等于6的组合有2组：1 + 5，2 + 4

输入描述：

第一行输入一个正整数N第二行输入M个不同的正整数，且正整数之间以一个英文逗号隔开

输出描述：

输出M个不同正整数中有多少组组合的和恰好等于N

样例输入：

5

1,2,3,4,5

样例输出：

2

02

二.思路分析

这是一道简单的算法题，涉及的知识点包括循环、列表、枚举算法等。

题目比较简单，其实就是两数之和问题，可以参考《两数之和-第12届蓝桥杯选拔赛Python真题精选》这篇教程。

之前也给出了三种典型的解决方案：

• 暴力枚举

• 组合函数

• 单循环遍历

这3种解法比较简单，这里就不再介绍了。除此之外，还可以使用对撞指针算法来实现。

所谓对撞指针，是指使用两个指针left、right分别指向列表第一个元素和最后一个元素，然后left指针不断递增，right不断递减，直到两个指针的值相撞（即 left== right）为止，如图：

使用对撞指针，可以将时间复杂度降低到O(n)，效率更高。

思路有了，接下来，我们就进入具体的编程实现环节。

三.编程实现

根据上面的思路分析，我们使用三种方法来编写程序：

• 枚举算法

• 组合函数

• 对撞指针

1. 枚举算法

枚举算法的思路，就是使用两层循环，找到所有的组合，代码如下：

2. 组合函数

使用combinations()函数可以直接获取两个数的组合，从而简化代码，如下：

3. 对撞指针

使用对撞指针的代码如下：

代码不多，说明两点：

1). 使用对撞指针，需要确保列表是有序的，所以需要先使用sort()进行排序；

2). 对于任意的两个指针left和right来说，分三种情况，如果两数和等于n时，将cnt加1，两个指针都前进一步，如果两数和小于n，left右移，否则right左移，直到两个指针撞到一起了，循环结束。

至此，整个程序就全部完成了，你可以输入不同的数据来测试效果啦。

四.总结与思考

本题代码在10行左右，涉及到的知识点包括：

• 循环语句；

• 列表操作；

• 枚举算法；

• 组合函数；

• 双指针算法；

本题代码不多，难度一般，关键点是要掌握多种解决方案，尽量提高算法效率。

相信你已经发现了，两数之和问题出现的频率还挺高的。实际上，它是经典的算法入门题目，在著名的Leetcode网站中，第一题就是两数之和。

题目虽然简单，但是解决方案比较多，非常考验我们的基本功。

枚举是最基本的方法，但是效率不高；组合函数是Python给我们的福利，使用起来非常方便；对撞指针则是巧妙的算法，可以极大地提升算法效率，当然还有一些其他的解决方案，比如哈希算法。

既然提到了Leetcode，超平老师就顺便给你留一道思考题，就是Leetcode的第一题，两数之和。

---

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2, 7, 11, 15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

---

你还有什么好的想法和创意吗，也非常欢迎和超平老师分享探讨。

如果你觉得文章对你有帮助，别忘了点赞和转发，予人玫瑰，手有余香😄

需要源码的，可以移步至“超平的编程课”gzh。