两次和运算,但目标在范围内

问题描述 投票:-1回答:1

我遇到了一个类似于旧的二和问题的问题,但是除了要求解一个值外,它还需要在一个范围内,而且我不确定如何有效地解决这个问题。这是我的问题的简化版本:

按优先顺序给出一个整数数组,找到前两个整数,它们的总和位于X和Y s.t的范围之间。 X <= sum <= Y(其中X

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

注意:按我的优先顺序,是指返回满足此条件的前两个整数

php arrays algorithm hash
1个回答
0
投票

您可以使用解决2和问题的二进制搜索方法,并调整二进制搜索功能以在一定范围内进行搜索。像这样的东西:

$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, $value, $min, $max) {
   $top = sizeof($array) -1;
   $bot = 0;
   while($top >= $bot) 
   {
      $p = floor(($top + $bot) / 2);
      if ($value+$array[$p] < $min) $bot = $p + 1;
      elseif ($value+$array[$p] > $max) $top = $p - 1;
      else return $array[$p];
   }
   return false;
}

输出:

Array
(
    [0] => 8
    [1] => 17
)
© www.soinside.com 2019 - 2024. All rights reserved.