查找具有给定总和的任意数量的不同连续子数组

Question

我有一个名为 $A 的数组，其中仅包含非零正数。

现在我需要找到任意数量的具有给定总和的不同连续子数组。

我会用例子来解释

$A = array(1, 2, 3, 4, 5);

我要找的总和是

5

。

然后是

(2, 3)

和

(5)

。

我尝试搜索并得到了Python代码。我已将其翻译为 PHP，但它无法工作

$s = 0;
for ($i = 0; $i < count($A); $i++) {
     for ($j = $i; $j < count($A); $j++) {
         $s = $s + $A[$j];
         if ($s == $sum) {
             echo "[" . $i . " " . $j . "]";
         }
     }
}

Answer 1

• count($A)

  ，你没有

  $B

• $s = 0;

  在第一个循环内
• 不要忘记

  $i

  和

  $j

  是索引，它们从

  0

开始
• 在开始搜索之前，不要忘记给

  $sum

  赋值

• if($s > $sum)

  您可能想从第二个循环开始

  continue;

祝你好运，
阿林

Answer 2

这会起作用：

$A = array(1, 2, 3, 4, 5);
$size = count($A);
$sum = 5;
$solution = array();
for($i = 0; $i < $size; $i++) {
    $tempsum = 0;
    for($j=$i; $j < $size && $tempsum < $sum; $j++) {
        $tempsum += $A[$j];
        if($tempsum === $sum) {
            $solution[] = array_slice($A, $i, $j - $i + 1);
        }
    }
}

var_dump($solution);

至于你的代码，有几个错误：

1. 每次循环中都必须重新初始化 $s。
2. 数组 $B 可能不存在（第二个循环停止条件）。
3. 当子数组的长度大于2时，将无法显示正确的结果。
4. 第二次循环不需要走到最后，只要临时和大于查找到的值就可以停止。

Answer 3

您需要在内循环开始时将

$s

初始化为

0

。

for($i = 0; $i < count($A); $i++){
    $s = 0;  // CHANGE HERE.
     for($j=$i; $j < count($A); $j++){
         $s = $s + $A[$j];
         if($s == $sum) {
             echo "[" . $i . " " . $j . "]";
         }
     }
}

Answer 4

这会起作用

<?php
    $a = array(1,2,3,4,5);

    $l = sizeof($a);

    for($i=0; $i<$l; $i++)
    {
        for($j=$i+1; $j<$l; $j++)
        {
            if($a[$i]+$a[$j] == 5)
                echo "( ".$a[$i]." , ".$a[$j]." ) <br/>";
        }
        if($a[$i]==5)
            echo "( ".$a[$i]." )<br/>";
    }
    ?>

Answer 5

$a = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11); // the array to search in
$b = array(); // the resulting array
$sum = 9; // the sum to search for

$w = $a; // $w is the working array which we may modify
$n = count($w); // number of elements in source array
for($i = 0; $i < $n; $i++){
    $x = 0;
    $t = array();
    if($w[$i] == $sum){
        $b[] = array($w[$i]);
    }
    if($w[$i] >= $sum){
        break;
    }
    for($j = $i; $j < $n; $j++){
        $x += $w[$j];
        $t[] = $w[$j];
        if($x == $sum){
            $b[] = $t;
        }
        if($x >= $sum){
            break; // already found the array, continue search
        }
    }
}

$b

将是：

array(3) {
  [0]=>
  array(3) {
    [0]=>
    int(2)
    [1]=>
    int(3)
    [2]=>
    int(4)
  }
  [1]=>
  array(2) {
    [0]=>
    int(4)
    [1]=>
    int(5)
  }
  [2]=>
  array(1) {
    [0]=>
    int(9)
  }
}