我一直在为这个我被要求回答的问题(从技术上讲是家庭作业)而汗流浃背。我考虑过一个哈希表,但我有点坚持我如何使这项工作的确切细节
这是问题:
给定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的奇数值。
谁能给我一个大致的方向,以便我可以更接近解决这个问题?