【刷题】找出数组中相加等于指定值的两个数据的下标

有一个数组a = [1,3,5-1,4]; 获取相加等于8的两个数据的下标,rst = [1,2]

最简单的办法就是套两层循环,但是空间时间和空间复杂度太高了,最坏的话都是O(n^2);

我们可以考虑用一层循环,思路为利用map,通过目标值8的反向相减当前值A得到想要的值B,进而通过Map拿到B的下标:

$arr = [1,3,5-1,4];
$map = [
    1  => 0,
    3  => 1,
    5  => 2,
    -1 => 3,
    4  => 4
];
第1次值为'1',下标为'0',8-1='7',获取key为7的下标,没有
第2次值为'3',下标为'1',8-3='5',获取key为5的下标,下标为'2'
得到结果[1,2]

列子:
function add($nums ,$target)
{
    $keys = array_keys($nums);
    $vals = array_values($nums);
    $map = array_combine($vals, $keys);

    foreach ($nums as $k => $numA) {
        $numB = $target - $numA;
        if (isset($map[$numB]) && $map[$numB] != $k) {
            return [$k, $map[$numB]];
        }
    }

    return [];
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×