[算法]找数组中和为定值的数组对

一道简单的算法题,要求在数组中,找到所有和为定值的数组对。比如在array(11,11,1,2,-1,3,4,6,7,8,9,5,-1)中,找到所有和为10的数组对。
考虑到时间复杂度,牺牲空间,每个值作为一个key,他的互补对为value-key,每遍历一个数组值,先判断有没有互补对,有则打印此key,和互补key,互补key-1,否则添加一个key.php代码如下:

<?php  
function findSum($arr, $sum) {  
    $total  = 0;  
    $sumArr = array();  
    foreach($arr as $key) {  
        //如果有此key,并且有和为sum的key,总数加一,失去一个互补key  
        if(isset($sumArr[$sum-$key]) && ($sumArr[$sum-$key] > 0)) {  
            $total ++ ;  
            //打印出来  
            $diff = $sum-$key;  
            echo "($key, $diff)</br>";  
            //互补key -1 
            $sumArr[$sum-$key] --;  
        }else{  
            //添加一个key  
            isset($sumArr[$key]) ?  $sumArr[$key]++ : ($sumArr[$key] = 1);  
        }  
    }  
    echo "total:{$total}";  
}  
//测试用例  
$arr = array(11,11,1,2,-1,3,4,6,7,8,9,5,-1);  
findSum($arr, 10);  

测试结果为:
(-1, 11)
(6, 4)
(7, 3)
(8, 2)
(9, 1)
(-1, 11)
total:6

发表评论

邮箱地址不会被公开。 必填项已用*标注


*