PHP基于指定关联数组按输入值匹配对应名称组合的实现咨询

实现逻辑 #

该需求对应经典的两数之和算法场景，以下提供两种适配不同场景的实现方案：

• 暴力枚举法：逻辑简单无额外空间消耗，适合本题这种元素数量少的数组场景
• 哈希表查找法：时间复杂度更低，适合元素数量多的业务场景

暴力枚举法实现（适合小数据量） #

<?php
// 预设关联数组
$groups_name = array("jhon"=>"20", "aliza"=>"30", "rehana"=>"40", "adiba"=>"50", "black"=>"1000", "white"=>"7500", "red"=>"3500");

/**
 * 匹配权重和等于目标值的两个名称
 * @param array $groups 预设的名称-权重关联数组
 * @param int $target 输入的目标总和
 * @return array 匹配到的名称对，无匹配返回空数组
 */
function matchTwoGroups($groups, $target) {
    $names = array_keys($groups);
    $len = count($names);
    // 双重遍历避免重复匹配
    for ($i = 0; $i < $len; $i++) {
        $weight1 = (int)$groups[$names[$i]];
        for ($j = $i + 1; $j < $len; $j++) {
            $weight2 = (int)$groups[$names[$j]];
            if ($weight1 + $weight2 == $target) {
                return [$names[$i], $names[$j]];
            }
        }
    }
    return [];
}

// 测试示例
$test1 = matchTwoGroups($groups_name, 50);
$test2 = matchTwoGroups($groups_name, 70);
$test3 = matchTwoGroups($groups_name, 4500);
print_r($test1); // 输出 Array ( [0] => jhon [1] => aliza )
print_r($test2); // 输出 Array ( [0] => jhon [1] => adiba )
print_r($test3); // 输出 Array ( [0] => black [1] => red )
?>

哈希表法实现（适合大数据量） #

如果后续数组元素数量大幅增长，可改用时间复杂度更低的哈希表方案：

function matchTwoGroupsHash($groups, $target) {
    $weightMap = [];
    foreach ($groups as $name => $weight) {
        $weight = (int)$weight;
        $diff = $target - $weight;
        // 检查差值是否已经存在于哈希表中
        if (isset($weightMap[$diff])) {
            return [$weightMap[$diff], $name];
        }
        // 不存在则将当前权重和名称存入哈希表
        $weightMap[$weight] = $name;
    }
    return [];
}

注意事项 #

• 代码中已做了权重的整型强制转换，避免原数组值为字符串时出现计算错误
• 以上实现默认返回第一组匹配到的结果，如果需要返回所有符合条件的配对，只需将return改为将结果推入结果数组，遍历结束后统一返回即可

内容的提问来源于stack exchange，提问作者Qaiser420