php - PHP函数或算法查找数组中的哪些元素加起来正好等于某个数字

Question

您好我正在寻找一种算法或函数来查找数组中的哪些元素组加起来达到一定数量。可能不止一个，所以我希望返回数组中从左到右读取的第一个好的组。

例如，假设我有一个随机数数组... $x = array(500, 90, 50, 200, 10, 300, 900) 我希望识别任何一组数组元素加起来等于给定数 X ，比如说 1,000。

在这种情况下，数组 $x 的元素 0,3,5 是第一个加起来为 1,000 (500 + 200 + 300) 的元素。元素 1,4,6 也加起来 1,000 (90 + 10 + 900) 但不是第一个，所以我们可以忽略它们。该函数应返回具有正确索引位置的新数组 $y = array(0,3,5)。

任何帮助表示赞赏！谢谢 ：-）

Answer 1

好的，我可能错过了这样做的“正确”方式，但我仍然有一些解决方案。

无限搜索 - 尝试 2（推荐）：

function get_parts3($arr,$target)
{
    foreach($arr as $k => $v)
    {
        if($v>$target) continue;
        foreach($arr as $k2 => $v2)
        {
            if($v2>$target) continue;
            if($k2==$k) continue;
            if($v + $v2 == $target)
            {
                return array($k,$k2);
            }
        }
        $tmparr = $arr;
        $tmparr[$k] = $target+1;
        $test = get_parts3($tmparr,$target-$v);
        if(is_array($test))
        {
            return array_merge(array($k),$test);
        }
    }
    return false;
}

尝试了无限搜索 1 - 但是在大型数组上可能会出现性能问题。

function get_parts2($arr,$target)
{
    foreach($arr as $k => $v)
    {
        if($v > $target) continue;
        $keys = array_keys($arr);
        for($i=0;$i<25;$i++)
        {
            $sum = $v;
            $parts = array();
            $parts[$k] = $v;
            foreach($keys as $k2)
            {
                if($k2 == $k) continue;
                $v2 = $arr[$k2];
                if($sum+$v2 > $target) continue;
                $sum += $v2;
                $parts[$k2] = $v2;
                if($sum==$target) return array_keys($parts);
            }
            shuffle($keys);
        }
    }
    return false;
}

有限搜索（在这种情况下是 2 或 3 个数字的组合）：

function get_parts($arr,$target)
{
    foreach($arr as $k => $v)
    {
        if($v>$target) continue;
        foreach($arr as $k2 => $v2)
        {
            if($v2>$target) continue;
            if($k2==$k) continue;
            if($v + $v2 == $target)
            {
                return array($v,$v2);
            }
            foreach($arr as $k3 => $v3)
            {
                if($v3>$target) continue;
                if($k3==$k2 || $k3==$k) continue;
                if($v + $v2 + $v3 == $target)
                {
                    return array($k,$k2,$k3);
                }
            }
        }
    }
    return false;
}