php 如何为数组创建函数

06odsfpq 于 2023-06-20 发布在 PHP

关注(0)|答案(1)|浏览(86)

我需要一个函数来查找数对，这些数对加起来等于数组的数组中给定的目标和。下面是一个示例数组：

array:10 [
  0 => array:2 [
    0 => 6
    1 => 3
  ]
  1 => array:2 [
    0 => 7
    1 => 5
  ]
  2 => array:2 [
    0 => 9
    1 => 5
  ]
  3 => array:2 [
    0 => 12
    1 => 4
  ]
  4 => array:2 [
    0 => 61
    1 => 1
  ]
  5 => array:2 [
    0 => 62
    1 => 1
  ]
  6 => array:2 [
    0 => 63
    1 => 1
  ]
  7 => array:2 [
    0 => 84
    1 => 5
  ]
  8 => array:2 [
    0 => 85
    1 => 4
  ]
  9 => array:2 [
    0 => 127
    1 => 5
  ]
]

这里有一个目标总和的例子：

$target = 32;

以下是我目前为止的函数：

public function findNumberCombination($array, $targetSum)
{
    $foundPairs = [];
    $n = count($array);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            $pairSum = $array[$i][1] + $array[$j][1];
            if ($pairSum == $targetSum) {
                $foundPairs[] = [$array[$i][0], $array[$j][0]];
            } else {
                for ($k = $j + 1; $k < $n; $k++) {
                    $pairSum = $array[$i][1] + $array[$j][1] + $array[$k][1];
                    if ($pairSum == $targetSum) {
                        $foundPairs[] = [$array[$i][0], $array[$j][0], $array[$k][0]];
                    } else {
                        // continue checking larger combinations
                    }
                }
            }
        }
    }
    return $foundPairs;
}

代码适用于所提供的示例，返回正确的对，但我需要修改它以处理具有更多嵌套数组的更大数组。有没有一种更有效、更可扩展的方法来解决这个问题？

php

来源：https://stackoverflow.com/questions/76493397/how-to-create-function-for-array

1条答案

按热度按时间

a8jjtwal1#

我在评论中提到的递归策略的一个例子：

function findsums($input, $sum, $start=0) {
    for( 
        $i = $start, $c = count($input);
        $i < $c;
        ++$i
    ) {
        $cur = $input[$i];
        $rem = $sum - $cur;
        
        // bounds    
        if( $rem == 0 ) {
            // this is the last element
            yield [$cur];
            return;
        } else if( $rem < 0 ) {
            // $cur too big
            return;
        } else if( array_sum(array_slice($input, $i+1)) < $sum ) {
            // all the remaining items in the input add up to less than the sum
            return;
        }
        
        foreach( findsums($input, $rem, $i+1) as $answer ) {
            yield array_merge([$cur], $answer);
        }
    }
}

$input = range(1,10);

foreach( findsums_new($input, 13) as $result ) {
    printf("%d: %s\n", array_sum($result), json_encode($result));
}

输出：

13: [1,2,3,7]
13: [1,2,4,6]
13: [1,2,10]
13: [1,3,4,5]
13: [1,3,9]
13: [1,4,8]
13: [1,5,7]
13: [2,3,8]
13: [2,4,7]
13: [2,5,6]
13: [3,4,6]
13: [3,10]
13: [4,9]
13: [5,8]
13: [6,7]

**edit：**我已经把原来的实现换成了一个对堆栈更金德的实现，并且稍微改进了边界检查。

作为参考，原始代码如下，但也包括改进的边界检查。

function findsums($input, $sum, $start=0) {
    $cur = $input[$start];
    $rem = $sum - $cur;

    // bounds    
    if( $rem == 0 ) {
        // this is the last element
        yield [$cur];
        return;
    } else if( $rem < 0 ) {
        // $cur too big
        return;
    } else if( array_sum(array_slice($input, $start+1)) < $sum ) {
        // all the remaining items in the input add up to less than the sum
        return;
    }
    
    // yield all [cur] + sub-array answers
    foreach( findsums($input, $rem, $start+1) as $answer) {
        yield array_merge([$cur], $answer);
    }

    // yield all sub-array answers
    yield from findsums($input, $sum, $start+1);
}

这个问题是它在堆栈上保留了更多的开放调用，这可能会成为处理更大集合的问题。除此之外，我相信所有其他性能指标大致相当。

赞(0）回复(0）举报 2023-06-20

我来回答

php 如何为数组创建函数

1条答案

相关问题

热门标签

最新问答