如何计算从四个等长数组各选一个元素和为指定值的方案数？

问题1：求各选一个元素和为k的方案数 #

暴力枚举所有四元素组合的时间复杂度是O(n⁴)，n较大时完全不可行，用分治法可将复杂度降至O(n²)，具体步骤：

• 先处理前两个数组A、B：遍历所有A[i] + B[j]的可能和，用哈希表sum_ab记录每个和值出现的次数，比如sum_ab[s]代表A、B中选元素和为s的组合数量。
• 再处理后两个数组C、D：遍历所有C[k] + D[l]的可能和s2，对每个s2，查找sum_ab[k - s2]的数值，将其累加到总方案数中——因为s1 + s2 = k等价于s1 = k - s2，每一组这样的(s1,s2)对应一组符合条件的四元素组合。

以你给出的示例为例：四个数组均为[1,1,1]，A+B的和只能是2，出现次数为3×3=9；C+D的和同样是2，出现次数9。当k=4时，k - s2 = 4-2=2，sum_ab[2]=9，总方案数为9×9=81，与示例结果一致。

问题2：统计所有元素和相同的选法数量 #

如果要统计每个可能和值对应的选法数，基于分治法扩展：

• 先得到sum_ab（A+B的和频次）和sum_cd（C+D的和频次）两个哈希表。
• 遍历sum_ab的每个键值对s1: cnt1，再遍历sum_cd的每个键值对s2: cnt2，则和值s = s1 + s2对应的选法数为cnt1 × cnt2，将该值累加到对应和值的统计字典中。
• 最终统计字典的键为所有可能的和值，值为该和值对应的四元素组合数。

如果是要统计所有和值对应的选法数总和，其实就是所有四元素组合的总数，即n⁴——因为每个组合都对应一个唯一的和值，总和就是全部可能的组合数量。

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