Кодовый код PHP – головоломка — D104 167. Две суммы II – Входной массив отсортирован

Автор оригинала: David Wong.

Ссылки на Темы

167. Две суммы II – Входной массив отсортирован

Анализ темы

Учитывая массив отсортированных целых чисел, найдите из него два числа и сложите их до заданного числа.

Возвращает индекс, соответствующий этим двум числам.

размышляющий

Первая мысль, которая приходит в голову, – это, конечно, прохождение одного за другим, но со временем. Давайте не будем вдаваться в подробности.

Затем я думаю об использовании дихотомии, чтобы найти позицию, меньшую, чем целевое число, чтобы уменьшить количество обходов.

Наконец, идея состоит в том, чтобы инвертировать данный массив и использовать его для поиска наличия указанной добавки.

Окончательный код

php
class Solution {

    /**
     * @param Integer[] $numbers
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($numbers, $target) {
        $repeatItems = array_filter(array_count_values($numbers),function($v){
            return $v>1;
        });
        $vs = array_flip($numbers);
        foreach($vs as $k => $v){
            if(isset($vs[$target-$k])){
                if(isset($repeatItems[$target-$k])){
                    return [$v, $v+1];
                }
                return [$v+1, $vs[$target-$k]+1];
            }
        }
        return [null, null];
    }
}

Если вы считаете, что эта статья полезна для вас, вы можете воспользоваться Фондом генерации энергии Ии.