check-sum.js

// Есть массив чисел
// Нужно выяснить есть ли в нем 2 числа сумма которых равна 18.
// сделать одним циклом

// два цикла O(n²)
function checkSum1(arr, sum = 18) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (j !== i && arr[i] + arr[j] === sum) {
                return true;
            }
        }
    }
    return false;
}


// два указателя, O(n²) при условии отсортированного массива
function checkSum2(arr, sum = 18) {
    const sorted = arr.sort((a, b) => a - b);
    let left = 0;
    let right = sorted.length - 1;

    while (left < right) {
        const currentSum = sorted[left] + sorted[right];
        if (currentSum === sum) {
            return true;
        } else if (currentSum < sum) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

// set O(n)
function checkSum(arr, sum = 18) {
    const prev = new Set();
    for (let num of arr) {
        const difference = sum - num;
        if (prev.has(difference)) {
            return true;
        }
        prev.add(num);
    }
    return false;
}


console.log(checkSum([0, 10, 12, 3, 8, 9], 18)); // true
console.log(checkSum([0, 10, 12, 3, 8, 9], 24)); // false
console.log(checkSum([0, 10, 12, 3, 8, 9, 12], 24)); // true