多组小数数组各取一数乘积命中指定区间的最优解法及全组合查找

问题规模前置说明 #

先明确极端场景的计算量边界：最多7个数组、单数组最长100个元素时，纯全量枚举的总组合数最高可达100^7 = 1e14，这种规模下暴力遍历完全不可行，必须采用低复杂度的折半枚举方案，结合排序、二分匹配实现最优求解。

核心算法选型：折半枚举 + 排序二分匹配（结合精度优化） #

该方案是目前这类多集合组合匹配问题的通用最优解法，时间复杂度已经贴近这类“找所有合法组合”问题的理论下界——毕竟输出所有合法解本身就需要至少O(E)的开销（E为合法解的总数量），不存在效率更高的通用求解逻辑。

具体执行步骤 #

• 动态拆分数组：根据每个数组的实际长度，将所有待选数组拆分为两组，保证两组分别枚举所有选数组合时的总组合量尽可能平衡（目标是让两组组合数的差值最小，整体把原本1e14的总计算量压缩到亿级以内）。比如7个长度均为100的数组，可拆分为一组3个数组、另一组4个数组，再根据实际数组长度微调拆分方式，让两边组合量都落在百万到千万级。
• 枚举单组所有组合：对拆分后的两组数组，分别递归枚举每个数组选一个元素的所有可能组合，计算每个组合的累计乘积值，过程中绑定记录每个乘积对应的所有元素在原数组中的索引，方便后续回溯输出具体选数方案。枚举时可结合提前剪枝：若当前累计乘积已经大于区间上限R（所有元素为正时），则无需继续枚举后续数组的选值，直接终止当前分支。
• 浮点精度优化：所有小数元素预先计算自然对数值，将原任务的乘积区间[L, R]等价转换为对数和区间[lnL, lnR]，全程用加法替代乘法计算，既减少计算开销，也避免多次乘法带来的浮点累计误差；由于对数是严格单调递增的，不会改变匹配结果的正确性。
• 排序与区间匹配：将其中一组生成的所有组合值（或对数值）做升序排序，排序过程中保留值和对应索引的绑定关系。遍历另一组的每一个组合值，计算需要匹配的目标值区间，利用二分查找快速定位排序后列表中落在目标区间内的所有元素，将两边的组合拼接即为合法解。

举个实际匹配的例子：当要求乘积区间为40~50时，第一组枚举得到组合a[2]*b[2] = 3*8 = 24，此时计算c数组中需要匹配的范围是40/24≈1.67到50/24≈2.08，c数组中取值为2的元素正好落在该区间，拼接后得到合法解a[2]*b[2]*c[1] = 48。

算法复杂度对比 #

• 纯暴力枚举：时间复杂度O(∏len_i)，极端场景下操作量达1e14，完全无法落地。
• 折半枚举+二分匹配：时间复杂度O(C1 + C2*logC2 + E)，其中C1、C2为两组分别枚举的组合量，E为最终输出的合法解数量。极端场景下操作量可控制在1e8级别，可在普通消费级硬件上快速运行。

特殊场景适配 #

• 数组含0值：单独判断乘积区间是否包含0，若包含则所有选到0的组合都是合法解；若不包含则在枚举阶段直接跳过选0的分支，无需参与后续匹配。
• 数组含负值：排序时将组合值拆分为正、负两个独立子列表分别排序。匹配时根据当前遍历的组合值的正负，调整不等号方向计算目标值区间（负值会反转大小关系），再分别在对应子列表中二分查找。
• 数组含大量重复值：预先统计相同元素的出现次数，枚举时直接复用计数结果，避免重复计算相同的组合值。

内容的提问来源于stack exchange，提问作者YD1m