algorithm - 在浮点数数组中找到一个三元组，它们的总和为 [1.0, 2.0] 中的一个值

Question

问题是：

给定一个浮点数数组，找到 3 个数字（不一定是连续的），它们的总和为一个由区间 [1.0, 2.0] 限制的值

这个问题发布在Triplet 的范围内 (1,2)和https://www.thetopsites.net/article/50729117.shtml。

后一个链接中的算法似乎与@Amitrajit Bose 在stackoverflow 问题中发布的算法相同。该算法本质上使用了一种贪心方法，如果总和大于 2.0，则丢弃您正在考虑的当前 3 个数字中的最大值，并将其替换为数组中的当前数字，如果总和小于 1.0，则替换当前 3 个数字中的最小数字。

这个算法好像错了？考虑 [0.2 0.2 1.7 0.5 0.05 0.05]。在这种情况下有几种解决方案，它们都必须使用 1.7，但该算法将使用数字 1.7 并得出结论，在给定的约束下不可能找到三元组。

我是不是误会了什么？

标签： algorithmlanguage-agnostic

Answer 1

是的你是对的。这种算法是错误的，您只是提供了一个失败的测试用例。

提到的算法：

1> Prepare the window of size 3 with the first 3 elements
2> IF (array.len <= 3): CHECK IF window-sum is in the range (1,2), then RETURN accordingly
3> FOR i = 3 UPTO (array.len-1)
3.1> SORT the window (3log3 = constant time operation)
3.2> IF window-sum is in the range (1,2): RETURN 1 or TRUE
3.3> ELSE IF window-sum < 1: Replace the smallest element in the window (window[0]) with array[i]
3.4> ELSE IF window-sum > 2: Replace the largest element in the window (window[2]) with array[i]
4> Outside the loop, check the FINAL window sum and RETURN accordingly.

另一个反例：[0.2, 0.3, 0.4, 1.5]
第一个窗口是[0.2, 0.3, 0.4]. 循环在索引wherefor开始和结束。已采取步骤，因此下一个窗口是. 算法结束时声称不存在总和在 中的这样的三元组。这种说法是错误的。3window_sum = 0.9 < 13.3[0.3, 0.4, 1.5]window_sum = 2.2 > 2[1.0, 2.0](0.2, 0.3, 1.5)2.0

旁注：该 stackoverflow 问题中还有一些不正确的答案。