<分区>
我在面试中被问到这个问题。
Given an array of ints, find all triplets whose sum is less than some number
经过一番摸索之后，我告诉面试官，最好的解决方案仍然会导致最坏情况下的运行时间 O(n3) 并且可能需要 O(n3) .
面试官公然反对我并告诉我“你需要回到你的算法......”。
我错过了什么吗？
<分区>
我在面试中被问到这个问题。
Given an array of ints, find all triplets whose sum is less than some number
经过一番摸索之后，我告诉面试官，最好的解决方案仍然会导致最坏情况下的运行时间 O(n3) 并且可能需要 O(n3) .
面试官公然反对我并告诉我“你需要回到你的算法......”。
我错过了什么吗？
最佳答案
一个可能的优化是:
sum的元素；O(N^2) 以获取 a[i] + a[j]，然后二进制搜索 sum - a[i] - 在[j + 1, N]范围内的a[j]，索引是可能的候选数，但是你应该减去j，因为他们已被覆盖。复杂度将是 O(N^2 log N)，稍微好一些。
关于arrays - "Find all triplets whose sum is less than some number"是否有比 O(n3) 运行时间更好的解决方案？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25670488/