8

我一直在为这个我被要求回答的问题(从技术上讲是家庭作业)而汗流浃背。我考虑过一个哈希表,但我有点坚持我如何使这项工作的确切细节

这是问题:

给定k组整数A 1 , A 2 ,.., A k的总大小为 O( n ),您应该确定是否存在 a 1 ϵ A 1 , a 2 ϵ A 2 ,.., a k ϵ A k ,使得a 1 + a 2 +..+ a k -1 = a k。您的算法应该在 T k ( n ) 时间内运行,其中 T k( n ) = O( n k /2 × log n ) 对于偶数k, O( n ( k +1)/2 ) 对于k的奇数值。

谁能给我一个大致的方向,以便我可以更接近解决这个问题?

4

1 回答 1

9

将 k 个集合分成两组。对于偶数 k,两组各有 k/2 组。对于奇数 k,一组有 (k+1)/2 组,另一组有 (k-1)/2 组。计算每组中所有可能的总和(从每组中取一个元素)。对于偶数 k,您将得到两个数组,每个数组都有 n k/2 个元素。对于奇数 k,一个数组有 n (k+1)/2个元素,另一个数组有 n (k-1)/2 个元素。问题简化为标准问题“给定两个数组,检查是否可以通过从每个数组中获取一个元素来达到指定的总和”。

于 2011-12-17T16:07:58.520 回答