0

Напишите программу (на языке JavaScript), которая найдет в массиве все пары целых чисел, сумма которых равна заданному значению.

Например:

Есть массив [1, 6, 5, 2, 7, 5, 1, 4, 3] и число 5. Пары чисел, которые должны быть найдены: (1:4), (2:3). Результат вывести в любом удобном для вас формате.

Будет плюсом, если пары чисел будут уникальными, т.е. (1:4) и (4:1) являются эквивалентными парами.

Написал такой вариант, но он повторяет значения, как избавиться от этого

var num = prompt('Введите число', '');
var arr = [1, 6, 5, 2, 7, 5, 1, 4, 3];

for (var i = 0; i < arr.length; i++) {
	for ( var j = 0; j < arr.length; j++) {
		if (arr[i] + arr[j] == num) {
			alert('Ваша пара чисел это ' + arr[i] + ' и ' + arr[j] + '.');
			console.log(arr[i], arr[j]);
		}
	}
}

3
  • Какие сложности у вас возникли при решении данной задачи ?
    – Mike
    12 фев 2018 в 17:18
  • и проблема ваша заключается в ...?
    – teran
    12 фев 2018 в 17:18
  • проблема в повторении пар чисел
    – it_lord
    12 фев 2018 в 17:28

6 ответов 6

5

Впервые что-то пишу на javascript. Прикольно, что любой объект - ассоциативная таблица. Это и использовал.

var num = prompt("Введите число", "5");
var arr = [1, 6, 5, 2, 7, 5, 1, 4, 3];
var tbl = {}

for (var i = 0; i < arr.length; i++)
  tbl[arr[i]] = (arr[i] in tbl) ? arr[i] + 1 : 1;

for (var v in tbl)
  if ((tbl[num - v] in tbl) && ((v < num - v) || ((v == num - v) && (tbl[v] > 1))))
      console.log("Ваша пара чисел: " + v + " + " + (num - v));

Пояснения:

  • Сначала все элементы массива используем в качестве ключей для ассоциативной таблицы (первый цикл). Попутно подсчитываем встречаемость каждого элемента в массиве.
  • Проходим по всем ключам таблицы (второй цикл). Для каждого ключа проверяем, существует ли в таблице другой ключ, который бы дополнял данное число до искомого: (tbl[num - v] in tbl). Если второй ключ есть - значит, обнаружено существование искомой пары. Если же ключ и "дополнение" равны, то требуем дополнительно, чтобы в массиве значение ключа встречалось неоднократно. Условие (v < num - v) - для "уникальности".
0

Не слишком алгоритмически оптимальный вариант, но зато демонстрирующий использование различных методов массива. :)

let num = +prompt('Введите число', '');
let arr = [1, 6, 5, 2, 7, 5, 1, 4, 3];

arr.sort().reduce((prev, cur) => { // удаляем из массива повторяющиеся элементы
    if (prev[prev.length - 1] != cur) {
      prev.push(cur);
    }
    return prev;
  }, [])
  .forEach((e, i, ar) => { // проходим по получившемуся массиву и для каждого элемента проверяем,.. 
    if (ar.slice(i + 1).some(el => el == num - e)) { // ...есть ли в оставшейся части массива элемент, дополняющий данный до заданного числа.
      console.log(e, num - e); // и если есть, то выводим найденную пару.
    }
  });
if (arr.indexOf(num / 2) > -1 && arr.indexOf(num / 2) != arr.lastIndexOf(num / 2)) { // дополнительно проверяем, были ли в исходном массиве 2 одинаковых элемента, дающие в сумме искомое число. 
  console.log(num / 2, num / 2);
}

0

Вот ещё один вариант поиска уникальных пар чисел

var num = 5;
var arr = [1, 6, 5, 2, 7, 5, 1, 4, 3, 9, 8, 11, 10, 18];
var result = [];

function deleteRepeat(array) { //удаляем повторения из массива
    var obj = {};

    for (var i = 0; i < array.length; i++) {
        var str = array[i];
        obj[str] = true;
    }

    return Object.keys(obj);
}

function find(array, number) { // ищем уникальные значения
    var x = null,
        y = null;
    array.forEach(function (i, value) {
        if(number - value < number) {
            x = number - value;

            array.forEach(function (j, value2) {
                if(x == value2 && j > i) {
                    y = value;

                    result.push(y +':' + x);
                }
            })
        }
    });
}

find(deleteRepeat(arr), num);

console.log(result);

0

Довольно оптимальное решение

function findPairs(nums, k) {  
    let sotedArray = nums.sort(compareNumbers);
    console.log(sotedArray);
    let result = [];
    let firstIndex = 0;
    let lastIndex = sotedArray.length - 1;
    while (firstIndex < lastIndex) {
        let currentSumm = sotedArray[firstIndex] + sotedArray[lastIndex];
        if (currentSumm == k) {
            let resultPair = sotedArray[firstIndex] + ':' + sotedArray[lastIndex];
            if (result.indexOf(resultPair) == -1) {
                result.push(resultPair);
            }
            firstIndex += 1;
            lastIndex -= 1;
        } else if (currentSumm < k) {
            firstIndex += 1;
        } else {
            lastIndex -= 1;
        }
    }
    return result;
}

function compareNumbers(a, b) {
    if (a > b) return 1;
    if (a == b) return 0;
    if (a < b) return -1;
}

let summ = 7;
let arr = [1, 6, 5, 2, 7, 5, 1, 3, 15, 4, 2, 18, 85];
console.log(findPairs(arr, summ));
1
  • добро пожаловать на Stack Overflow на русском! пожалуйста, постарайтесь оставлять чуть более развёрнутые ответы. дополнить ответ можно, нажав править 25 янв 2020 в 20:29
0

Когда-то делал гольф на эту тему: Код-гольф - Реализация алгоритма выборки комбинаций

Вот видоизменённое решение от @Qwertiy ♦:

let fn = (a, n) => [...Array(2e3)]
  .map((x, q) => a
    .filter((x, i) => q & 1 << i)
    .sort()
  ).sort()
  .filter((x, i, a) =>
    x + "" != a[i-1] & eval(x.join`+`) == n
  );

console.info(fn([1, 6, 5, 2, 7, 5, 1, 4, 3], 5)); // Найдены такие комбинации: 1,1,3  1,4  2,3  5
// Оставить только те, где ровно два числа можно фильтром: .filter(a => a.length === 2)
[1, 6, 5, 2, 7, 5, 1, 4, 3]
1;4
2;3

-1

var summ = prompt('Введите число', '');
var arr = [1, 6, 5, 2, 7, 5, 1, 3, 15, 4, 2, 18, 85];
var result = [];
var firstNum = null;
var secondNum = null;
var numbers = null;

arr.forEach(function (value, i) {
    firstNum = value;
    secondNum = summ - value;
    numbers = firstNum + ':' + secondNum;

    if(arr.indexOf(secondNum) >= i && result.indexOf(numbers) < 0){
        result.push(numbers);
    }
});

console.log(result);

1
  • с инглишем все критично
    – Gs D
    12 фев 2018 в 19:02

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.