Проблемы алгоритмов PHP — проблема №1.


Проблема

Если дан список чисел и число k, верните true, если в списке есть два числа, при сложении которых получается k.
Например, если дан список [10, 15, 3, 7] и k = 17, то возврат должен быть истинным, так как 10 + 7 равно 17.

Разрешение

Учитывая, что мы хотим найти два числа, которые при сложении дают одинаковое значение k, мы можем считать, что у нас есть простое выражение суммы, как показано ниже:

k = a + b
Войдите в полноэкранный режим Выход из полноэкранного режима

Это выражение можно переписать как:

a - k = b
Войдите в полноэкранный режим Выход из полноэкранного режима

В PHP существует как минимум три способа сделать это, я перечислю все три:

1 — Первый вариант и тот, который я считаю наименее идеальным, это использование array_flip и преобразование значений в ключи, что позволяет использовать isset в foreach.

$array = array_flip([10, 15, 3, 7]);
$k = 25;
    foreach ($array as $key => $num) {
        if (isset($array[$k - $key])) {
        echo 'true';
        break;
    }
}
Войдите в полноэкранный режим Выход из полноэкранного режима

2 — Мы все еще можем использовать foreach с массивом in_array, без необходимости использования array_flip.

$array = [10, 15, 3, 7];
$k = 25;
foreach ($array as $key => $num) {
    if (in_array($k - $key, $array)) {
        echo 'true';
    }
}
Войдите в полноэкранный режим Выход из полноэкранного режима

3 — Или используйте функцию, которая использует вложенные циклы для проверки значений.

/**
 * @param array $array
 * @param int $k
 * @return bool
 */
function twosum(array $array, int $k): bool
{
    foreach ($array as $key => $value) {
        foreach ($array as $key2 => $value2) {
            if ($value + $value2 == $k) {
                return true;
            }
        }
    }

    return false;
}

$array = [10, 15, 3, 7, 2];
$k = 17;
var_dump(twosum($array, $k));

Войдите в полноэкранный режим Выход из полноэкранного режима

Оцените статью
devanswers.ru
Добавить комментарий