我被要求回答这个问题（它实际上是作业），已经想过使用哈希表，但我卡在了如何精确地使其工作的细节上。
以下是问题：
给定k个整数集合A1，A2，...，Ak，总大小为O（n），您应该确定是否存在a1 ϵ A1，a2 ϵ A2，...，ak ϵ Ak，使得a1+a2+...+ak−1=ak。您的算法应在Tk（n）时间内运行，其中Tk（n）= O（nk/2 × log n）对于偶数k，O（n（k+1）/2）对于奇数k。
有人可以给我一个大致的方向，以便我更接近解决此问题吗？
是否存在K个整数的组合，它们的和等于给定的数字？
8
- Arnon
3
4恭喜你完成作业。你对这个问题有没有任何答案（不考虑复杂性）？如果有，你认为它的复杂度是多少？你觉得你的方法完全错误，还是只有某些部分有问题？ - Damien_The_Unbeliever
我唯一想到可以百分之百地解决问题的方法就是实现最简单和朴素的n^n算法（即检查所有选项）。显然，这不是正确的做法 :( - Arnon
1我在想这个问题是否更适合在数学溢出网站上提问？ - Jonathan Grynspan
1个回答
9
将k个集合分成两组。对于偶数k，两组每组有k/2个集合。对于奇数k，一组有(k+1)/2个集合，另一组有(k-1)/2个集合。计算每个组内所有可能的和（从每个集合中取一个元素）。对于偶数k，你将得到两个数组，每个数组都有nk/2个元素。对于奇数k，一个数组有n(k+1)/2个元素，另一个数组有n(k-1)/2个元素。这个问题被简化为标准问题：“给定两个数组，检查是否可以通过从每个数组中取一个元素来达到指定的和”。
- viswanathgs
4
谢谢你的回答！这个直觉上看起来是对的，但我还不能完全理解它是如何减少问题的。你能详细解释一下吗？ - Arnon
给定两个大小为O(n)的数组，您可以在O(n*log n)的时间内找到是否存在一个和。这个解决方案并不太困难。如果我把它透露给你，因为你提到了这是一项作业，我会感到有罪的！ - viswanathgs
@viswanathgs：你甚至可以在平均O(n)的时间内解决两个数组问题。 - Massimo Cafaro
@unforgiven：那只有在数组已排序的情况下才是这样，对吗？还是我漏看了什么？ - viswanathgs
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 5 给定一个包含 n 个整数的集合，返回所有元素数量为 k 的子集使得它们的和等于 0。
- 3 需要多少个数字使得它们的和等于整数N？
- 3 如何在实数集合 R 中找出所有可能的 k 个整数，它们的和等于某个特定的数字？
- 3 给定两个整数n和k，编写程序返回从1到n中选取k个数字的所有可能组合。
- 35 给定一个数字列表和一个数字k，返回列表中是否存在任意两个数字相加等于k。
- 10 获取所有可能的加和等于给定数字的组合
- 6 算法：检查数组S和T中是否存在整数s和t，使得s+t=k（k为给定数字）。 简化版：检查数组S和T中是否有两个数的和等于给定数字k。
- 4 在数组中找到乘积等于给定数字的k个元素
- 5 从二叉搜索树中找到两个数使它们的和等于给定的数字K
- 3 寻找最小的整数，使其数字平方的和等于给定的数字。