我一直在为我被要求回答的这个问题(这在技术上是家庭作业)而大费周章。 我已经考虑过哈希表,但我有点卡在我如何使它工作的确切细节上
问题是:
Given k sets of integers A1,A2,..,Ak of total size O(n), you should determine whether exist a1 ϵ A1, a2 ϵ A2,..,ak ϵ Ak, such that a1+a2+..+ak−1 =ak. Your algorithm should run in Tk(n) time, where Tk(n) = O(nk/2 × log n) for even k, and O(n(k+1)/2) for odd values of k.
任何人都可以给我一个大体方向,以便我可以更接近解决这个问题吗?
最佳答案
将k组分成两组。对于偶数 k,两组各有 k/2 组。对于奇数 k,一组有 (k+1)/2 组,另一组有 (k-1)/2 组。计算每组内所有可能的总和(从每组中取一个元素)。对于偶数 k,您将得到两个数组,每个数组都有 nk/2 个元素。对于奇数 k,一个数组有 n(k+1)/2,另一个数组有 n(k-1)/2 个元素。问题简化为标准问题“给定两个数组,检查是否可以通过从每个数组中取一个元素来达到指定的总和”。
关于algorithm - 是否存在 K 个整数的组合,使得它们的和等于给定的数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8545800/