两个求和问题，但目标在一个范围内

Question

我遇到了一个类似于旧的两个和问题的问题，但不是求解一个值，它需要在一个范围内，我不知道如何有效地解决这个问题。这是我的问题的简化版本：

给定一个按优先顺序排列的整数数组，找到其和位于 X 和 Y 范围之间的前两个整数 st X <= sum <= Y（其中 X < Y 并且已知，即任意 X=20 和 Y= 40)。

我已经使用 for 循环完成了蛮力方法，但我不确定这是否是最高效的解决方案。我考虑过使用哈希表，但我不知道如何应用它。

注意：按优先顺序，我的意思是，返回满足此条件的前两个整数

Answer 1

也许这是您已经尝试过的蛮力方法，但我认为这是最简单的方法。从前两个元素的子集开始，迭代大小增加的子集，比较子集中每个元素的值与最后一个元素的值的总和。当你在范围内找到一个总和时，你就完成了。这将根据“first”的定义找到范围内的第一对数字，即“具有最低最大索引的对”。function findFirstSumInRange(int $min, int $max, array $values = []): array{&nbsp; &nbsp; for ($b = 1, $n = count($values); $b < $n; $b++) {&nbsp; &nbsp; &nbsp; &nbsp; for ($a = 0; $a < $b; $a++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ($min <= ($sum = $values[$a] + $values[$b]) && $sum <= $max) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return [$values[$a], $values[$b]];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // or return [$a => $values[$a], $b => $values[$b]]; if you need the keys as well&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return [];}您可以通过跳过已经大于范围上限的任何值来加快速度。function findFirstSumInRangeB(int $min, int $max, array $values = []): array{&nbsp; &nbsp; for ($b = 1, $n = count($values); $b < $n; $b++) {&nbsp; &nbsp; &nbsp; &nbsp; if ($values[$b] < $max) { // else these sums will all be > the range because one addend is&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for ($a = 0; $a < $b; $a++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ($values[$a] < $max && $min <= ($sum = $values[$a] + $values[$b]) && $sum <= $max) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return [$a => $values[$a], $b => $values[$b]];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return [];}关于“性能最高的解决方案”，除非性能引起问题，否则我宁愿追求简单而不是优化性能。只是我的观点。

Answer 2

将每个元素添加到树状图中，键作为元素，值作为该元素出现的索引列表。在向树形图添加元素时，检查是否有一个子图，其键范围从X - current_element到Y - current_element两者都包含。如果您有子图，您的答案是[curr_element, A[first_index_of_submap's value_of_first_key] ]

Answer 3

您可以使用解决 2 sum 问题的二进制搜索方法，并调整您的二进制搜索功能以在一个范围内搜索。像这样的东西：$arr = [1,2,4,6,8,14,15,17];print_r(first_sum_in_range($arr, 25, 40));function first_sum_in_range($array, $min, $max){&nbsp; &nbsp; foreach ($array as $k=>$a) {&nbsp; &nbsp; &nbsp; &nbsp; $b = binary_search_range($array, $a, $min, $max);&nbsp; &nbsp; &nbsp; &nbsp; if ($b !== false) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return [$a,$b];&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}function binary_search_range($array, $a, $min, $max) {&nbsp; &nbsp;$top = sizeof($array) -1;&nbsp; &nbsp;$bot = 0;&nbsp; &nbsp;while($top >= $bot)&nbsp;&nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; $p = floor(($top + $bot) / 2);&nbsp; &nbsp; &nbsp; if ($a+$array[$p] < $min) $bot = $p + 1;&nbsp; &nbsp; &nbsp; elseif ($a+$array[$p] > $max) $top = $p - 1;&nbsp; &nbsp; &nbsp; else return $array[$p];&nbsp; &nbsp;}&nbsp; &nbsp;return false;}输出：Array(&nbsp; &nbsp; [0] => 8&nbsp; &nbsp; [1] => 17)