有没有办法在比O(n^3)更好的时间内解决4Sum问题?



>问题:给定一个包含 n 个整数和一个整数目标的数组,数字中是否存在元素 a、b、c 和 d,使得 a + b + c + d = 目标?在数组中找到所有唯一的四胞胎,给出目标的总和。

所以有一个明显的 n^3 解决方案,带有排序,两个嵌套的循环然后检查。

但是有没有办法做得更好?请注意,这不是决策问题,只需查看是否存在解决方案,而是返回所有唯一的四胞胎。

不,不可能以比O(n^3)时间复杂度更有效的方式找到所有独特的四胞胎。但是,如果您只想计算四倍的数量而不是列出,那么在时间复杂度O(n^2)这是可能的。

最新更新