我需要一个函数来查找数对,这些数对加起来等于数组的数组中给定的目标和。下面是一个示例数组:
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;
}
代码适用于所提供的示例,返回正确的对,但我需要修改它以处理具有更多嵌套数组的更大数组。有没有一种更有效、更可扩展的方法来解决这个问题?
1条答案
按热度按时间a8jjtwal1#
我在评论中提到的递归策略的一个例子:
输出:
**edit:**我已经把原来的实现换成了一个对堆栈更金德的实现,并且稍微改进了边界检查。
作为参考,原始代码如下,但也包括改进的边界检查。
这个问题是它在堆栈上保留了更多的开放调用,这可能会成为处理更大集合的问题。除此之外,我相信所有其他性能指标大致相当。