Является ли этот алгоритм сортировки правильным?

Question

Я пытаюсь задать вопрос 2.3-7 в CLRS, в котором говорится:

Опишите алгоритм тэта (n log (n)) - времени, который, учитывая набор S из n целых чисел и другое целое число x, определяет, существуют ли два элемента в S, сумма которых точно равна x.

Мой алгоритм следующий:

1. Sort(S)
2. S' = x - Sort(S)  (subtracts x from each element in sorted S) 
3. for each y in S' check if y in Sort(S) if not return NIL
4. For a y satisfying condition 3 let S'' = Sort(S)+y
5. Return the index of value v in S'' which equals x and return (v-y,y) from S

Это, кажется, работает в тета (n lg (n)) время, потому что мы можем сделать

1. В тета (n (lg (n)) раз с сортировкой слиянием
2. В O (n) время
3. В тета (nlg (n)) время Бинарный поиск для каждого из n элементов в S '
4. В O (n) время
5. В O (n) время

Сумма равна тета (n log (n)). Это правильно?

Answer 1

Это можно сделать за линейное время с O (n) пространственной сложностью, используя HashMaps.

    private Boolean testElementSum(List<Integer> list, int sumNumber) {
        HashMap<Integer, Boolean> map = new HashMap<>();
        for (int x : list) {
            if (map.containsKey(x))
                return (map.get(x));

            map.put(sumNumber - x, true);
        }
        return false;
    }

    @Test
    private void testSum() {
        List<Integer> list = Arrays.asList(1, 2, 3, 9, 20, 33);
        Assert.assertTrue(testFummy(list, 29));
        Assert.assertTrue(testFummy(list, 3));
        Assert.assertTrue(testFummy(list, 53));
        Assert.assertTrue(testFummy(list, 12));
        Assert.assertFalse(testFummy(list, 100));
        Assert.assertFalse(testFummy(list, 0));
    }