Skip to content

Latest commit

 

History

History
185 lines (126 loc) · 7.4 KB

numbers_sum.md

File metadata and controls

185 lines (126 loc) · 7.4 KB
Raw

Поиск двух чисел из отсортированного массива, в сумме дающих заданное число

Условие

Нам дан отсортированный массив чисел и некоторое число K. Необходимо найти два числа из массива, в сумме дающих число K. Если таких чисел нет, то вернуть пустой массив. Если таких чисел несколько, то вернуть любую пару чисел, удовлетворяющих условию задачи.

Использовать дважды одно и то же число нельзя!

Примеры

[-1, 2, 5, 8], K = 7

Ответ: [-1, 8]
[2, 4, 5], K = 8

Ответ: []
[-2, -1, 1, 2], K = 0

Ответ: [-2, 2]

Решение

Решение перебором

Решение в лоб, простым перебором пар.

Будем суммировать пары чисел по порядку до первой пары, которая выполняет условие задачи. Если дошли до конца массива - значит нет нужных нам пар и возвращаем пустой массив.

    public static int[] allPairsEnumeration(int[] arr, int k) {
        for (int i = 0; i < arr.length; i++) {
            var item = arr[i];

            for (int j = i + 1; j < arr.length; j++) {
                var item2 = arr[j];

                if (item + item2 == k) {
                    return new int[] {item, item2};
                }
            }
        }

        return new int[] {};
    }

Время работы: O(N^2)

Память: O(1)

Решение через Set

Предыдущее решение было O(N^2), поэтому попробуем улучшить наш алгоритм.

Объявим кеш из которого мы сможем достать за O(1) необходимый нам элемент. Для данной задачи отлично подойдет HashSet.

Заметим, что мы можем оперировать нашим искомым числом k. Возьмем первое число в массиве и вычтем его из k, таким образом получим то число, которое мы должны найти в пару.

Проверим, есть ли такое число у нас в кеше (проверка у нас быстрая). Если такого числа нет, то поместим текущее число в кеш. Теперь, если это число сможет стать парой для другого мы сможем быстро найти его в кеше, а не перебирать весь массив снова.

Например, у нас есть массив [2, 3, 5] и ищем мы 7.

Создаем кеш (пока он пустой).

Берем 2 и вычитаем из искомого это число, получаем 5-ку. Ищем 5-ку в кеше. Пока в кеше у нас нет элементов и 5-ку мы не находим. Кладем 2-ку в кеш, чтобы при необходимости достать ее за O(1).

Берем 3-ку и ищем в кеше для нее 4-ку, как подходящую пару. Не находим, поэтому кладем в кеш 3-ку.

Берем 5-ку и ищем в кеше 2-ку, успешно ее находим (она у нас с первой итерации в кеше) и возвращаем нашу пару.

    public static int[] withSet(int[] arr, int k) {
        var cache = new HashSet<Integer>();

        for (int item : arr) {
            var num = k - item;

            if (cache.contains(num)) {
                return new int[]{item, num};
            } else {
                cache.add(item);
            }
        }

        return new int[] {};
    }

Время работы: O(N)

Память: O(N)

Решение через бинарный поиск

Вспомним, что по условию задачи массив отсортирован.

Возьмем число в массиве и вычтем его из k, таким образом получим то число, которое мы должны найти в пару. Попробуем найти искомое с помощью бинарного поиска, ведь массив у нас отсортирован по условиям задачи.

    public static int[] binarySearch(int[] arr, int k) {

        for (int i = 0; i < arr.length; i++) {
            var num = k - arr[i];

            int left = i + 1;
            int right = arr.length - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2;

                if (num == arr[mid]) {
                    return new int[]{arr[i], num};
                } else if (num > arr[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return new int[] {};
    }

Бинарный поиск работает за O(log2(N)), так как каждый раз мы делим искомый массив напополам. Поиск мы применяем в цикле, т.е. в худшем случае мы воспользуемся им N раз.

Время работы: O(N * log2(N))

Память: O(1)

Решение через два указателя

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

Сложим оба числа и сравним с искомым k.

  • Если сумма равна, то это те числа, что мы ищем
  • Если сумма меньше, то мы можем сдвинуть левый указатель вправо, так как даже в сумме с максимальным числом в массиве результат оказался меньше искомого
  • Если сумма больше, то мы можем сдвинуть правый указатель влево

Сделаем это в цикле и найдем искомую пару!

Грубо говоря, создадим окно в котором ищем пару. Двигаем окно и смотрим если сумма меньше, двигаем правую часть, если сумма больше двигаем левую часть.

    public static int[] twoPointers(int[] arr, int k) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            if (arr[left] + arr[right] == k) {
                return new int[]{arr[left], arr[right]};
            } else if (arr[left] + arr[right] < k) {
                left++;
            } else {
                right--;
            }
        }

        return new int[]{};
    }

Время работы: O(N)

Память: O(1)