面试题之相关算法题整理(php语言实现版)

1、第一题

有一个整数数组 例如：[3, 2, 7, 9, 5, 1, 0, 4]，写一个程序 找出该数组中的任意两个数的和(sum)，是某个数指定的数，比如，sum是6的话，需要找到（5，1）以及（2，4）。

/*
采用冒泡排序方式，只不过这次是利用冒泡排序的方法查找符合条件的数组元素 而不是进行排序。即每一个元素都会和剩下的所有元素进行相加 如果结果和$sum相等 则当前2个元素符合条件 则进行保留
 */
function sumStatistical($array, $sum)
{
    $result = [];

    $length = count($array);

    for($i = 0; $i < $length; $i++)
    {
        for($j = $i + 1; $j < $length; $j++)
        {
            if($array[$i] + $array[$j] == $sum)
            {
                $result[] = [$array[$i], $array[$j]];
            }
        }
    }

    return $result;
}

$arr = [3, 2, 7, 9, 5, 1, 0, 4];
$sum = 6;
print_r(sumStatistical($arr, $sum));
/*
Array
(
    [0] => Array
        (
            [0] => 2
            [1] => 4
        )

    [1] => Array
        (
            [0] => 5
            [1] => 1
        )
)
*/




/*************第二种实现方式****************/
/*
这个函数遍历给定的$array数组 对于每个元素计算目标($sum) 和 与当前遍历到的元素之间的差值（即补数）。
如果补数存在于哈希表中 则找到了一对满足条件的数，则将其添加到结果数组中。同时 每次将遍历到的每个元素自身作为键值对 存入哈希表中 以备后续查找时使用。
 */
function sumStatistical2($array, $sum)
{
    $result   = [];
    $hasTable = [];

    foreach($array as $key => $val)
    {
        $diff = $sum - $val;

        if(isset($hasTable[$diff]))
        {
            $result[] = [$hasTable[$diff], $val];
        }

        $hasTable[$val] = $val;  //将当前值存入到hasTable数组中 以便后续每次循环的时候 查找其具体的补数
    }

    return $result;
}

$arr = [3, 2, 7, 9, 5, 1, 0, 4];
$sum = 4;
print_r(sumStatistical2($arr, $sum));
/*
Array
(
    [0] => Array
        (
            [0] => 3
            [1] => 1
        )

    [1] => Array
        (
            [0] => 0
            [1] => 4
        )
)
*/

233

声明：禁止任何非法用途使用，凡因违规使用而引起的任何法律纠纷，本站概不负责。