Подправить алгоритм

Question

Задача: Дан массив целых чисел, необходимо вернуть индексы двух чисел, сумма которых равна заданному числу. Можно считать, что массив будет иметь ровно одно решение. Нельзя использовать одно и то же число дважды.

Пример1: [2, 7, 11, 15], 9
Ответ: [0, 1]

Пример2: [3, 2, 4], 6
Ответ: [1, 2]

Если считать, что массив упорядочен (в условии этого нет!), то решаю методом двух указателей:

    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1;

        while (l < r) {
            int currentSum = nums[l] + nums[r];

            if (currentSum == target) {
                return new int[]{l, r};
            } else if (currentSum > target) {
                r--;
            } else if (currentSum < target) {
                l++;
            }
        }

        throw new RuntimeException("the pair is not found");
    }

Сложность O(n).

Но тут проблема со вторым примером:

Пример2: [3, 2, 4], 6
Ответ: [1, 2]

Должен выдать 1,2 а у меня исключение вылетает. Подскажите, как подправить алгоритм для случая, когда массив неупорядоченный?

Answer 1

Да никак не подправить. Или сортировать, или использовать другой алгоритм - в простейшем случае два цикла с квадратичным времени, либо использовать хэш-таблицу, тогда время линейное, но памяти O(n)

Answer 2

Если сортировка не рассматривается как вариант, то наиболее простое решение без использования дополнительных структур данных, проверка во вложенных циклах:

public static int[] twoSum(final int target, int ... nums) {
    for (int i = 0, n = nums.length; i < n - 1; i++) {
        int a = nums[i];
        for (int j = i + 1; j < n; j++) {
            int b = nums[j];
            if (target == a + b) {
                return new int[]{i, j};
            }
        }
    }
    
    throw new RuntimeException("the pair is not found");
}

Вариант решения, если можно использовать хэш-таблицы:

public static int[] twoSum(final int target, int ... nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0, n = nums.length; i < n; i++) {
        int a = nums[i];
        int b = target - a;
        if (map.containsKey(a)) {
            return new int[]{map.get(b), i};
        }
        map.put(a, i);
        map.computeIfAbsent(b, k -> -1);
        System.out.println("i=" + i + "; map=" + map);
    }
    
    throw new RuntimeException("the pair is not found");
}

Answer 3

Спасибо за подсказку с HashMap! Вот итоговое правильное решение (система его приняла):

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int key = target - nums[i];

            if (map.containsKey(key) && i != map.get(key)) {
                return new int[]{i, map.get(key)};
            }
        }

        throw new RuntimeException("the pair is not found");
    }

БЛОГ НА HUSL

Подправить алгоритм

Ответы (3 шт):