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

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

{

    for ($b = 1, $n = count($values); $b < $n; $b++) {

        for ($a = 0; $a < $b; $a++) {

            if ($min <= ($sum = $values[$a] + $values[$b]) && $sum <= $max) {

                return [$values[$a], $values[$b]];

                // or return [$a => $values[$a], $b => $values[$b]]; if you need the keys as well

            }

        }

    }

    return [];

}

您可以通过跳过已经大于范围上限的任何值来加快速度。

function findFirstSumInRangeB(int $min, int $max, array $values = []): array

{

    for ($b = 1, $n = count($values); $b < $n; $b++) {

        if ($values[$b] < $max) { // else these sums will all be > the range because one addend is

            for ($a = 0; $a < $b; $a++) {

                if ($values[$a] < $max && $min <= ($sum = $values[$a] + $values[$b]) && $sum <= $max) {

                    return [$a => $values[$a], $b => $values[$b]];

                }

            }

        }

    }

    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){

    foreach ($array as $k=>$a) {

        $b = binary_search_range($array, $a, $min, $max);

        if ($b !== false) {

            return [$a,$b];

        }

    }

}

function binary_search_range($array, $a, $min, $max) {

   $top = sizeof($array) -1;

   $bot = 0;

   while($top >= $bot) 

   {

      $p = floor(($top + $bot) / 2);

      if ($a+$array[$p] < $min) $bot = $p + 1;

      elseif ($a+$array[$p] > $max) $top = $p - 1;

      else return $array[$p];

   }

   return false;

}

输出：

Array

(

    [0] => 8

    [1] => 17

)