Давайте обсудим, грубый-лучше-оптимальный подход

Перебор — с использованием ДВУХ ЦИКЛОВ
Лучше — с использованием SET
Оптимальный — Сортировка + ДВА УКАЗАНИЯ

Input Format: N = 5, arr[] = {2,6,5,8,11}, target = 14
Result: YES (for 1st variant) [1, 3] (for 2nd variant)

Explanation: arr[1] + arr[3] = 14. So, the answer is “YES” for the first variant and [1, 3] for 2nd variant.

Брут (Используя 2 петли)

  • Для каждого индекса i мы будем проходить через оставшийся массив, используя другой цикл (скажем, j), чтобы найти другое число, чтобы сумма была равна цели (т.е. arr[i] + arr[j] = target).

Временная сложность: O(N2), есть два цикла (т.е. вложенные), каждый из которых выполняется примерно N раз.
Вспомогательное пространство:O(1) s мы не используем дополнительное пространство.

for (i = 0; i < (size - 1); i++) {
    for (j = (i + 1); j < size; j++) {

        if (A[i] + A[j] == target) { 
            return true;
        }
    }
 }

Output: This is the answer for variant 2: [1, 3]

Лучше использовать Set

  • Выберите элемент массива один за другим
  • Проверить наличие target-arr[i]на карте. Если этого элемента не существует, мы просто сохраним текущий элемент в hashMap вместе с его индексом. Если такой элемент существует, мы вернем «ДА.

Временная сложность: O(N), так как весь массив необходимо пройти только один раз.
Вспомогательное пространство: O(N), хэш-карта имеет используется для хранения элементов массива.

function twoSum(arr, target) {
    let s = new Set();
    for (let i = 0; i < arr.length; ++i)
    {
        let temp = target - arr[i];

        // checking for condition
        if (s.has(temp)) {
            document.write(
                "Pair with given sum "
                + sum + " is (" + arr[i]
                + ", " + temp + ")");
        }
        s.add(arr[i]);
    }
}

Output: This is the answer for variant 2: [1, 3]

Оптимальный — два указателя (сортировка)

  • Сначала мы отсортируем массив
  • Мы сохраним указатель left у первого индекса и указатель right у последнего индекса. Теперь, пока влево ‹ вправо, мы проверим сумму arr[left] и arr[right].
  1. Если arr[left] + arr[right] › sum, мы уменьшаем правый указатель.
  2. Если arr[left] + arr[right] ‹ sum, мы увеличим левый указатель.
  3. Если arr[left] + arr[right] == ​​sum, мы вернем результат.

Временная сложность: O(NlogN), Временная сложность для сортировки массива
Вспомогательное пространство: O(1)

function twoSum(arr, arr_size, target) {
    var left, right;
 
    /* Sort the elements */
    arr.sort();
 
    /* Now look for the two candidates in the sorted array*/
    l = 0;
    r = arr_size - 1;
    while (l < r) {
        if (arr[l] + arr[r] == target)
            return 1;
        else if (arr[l] + arr[r] < target)
            l++;
        else // arr[i] + arr[j] > target
            r--;
    }
    return 0;
}

Output: This is the answer for variant 2: [1, 3]

Ссылка