Разработка алгоритма, обнаруживающего в массиве все пары целых чисел, сумма которых равна заданному значению

228

14 февраля 2018, 13:17

Напишите программу (на языке 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]); 
		} 
	} 
}

Answer 1

Впервые что-то пишу на 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) - для "уникальности".

Answer 2

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

Вот видоизменённое решение от @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

Answer 3

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

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); 
}

Answer 4

var num = prompt('Введите число', '');
var arr = [1, 6, 5, 2, 7, 5, 1, 4, 3];
var nums_searched = [];
for (var i = 0; i < arr.length; i++) {
    var one_num = arr[i];
    var two_num = num - arr[i];
    var result = one_num+":"+two_num;
    if(arr.indexOf(two_num)>=i && nums_searched.indexOf(result)<0){
        nums_searched.push(result);
        console.log(result);
    }
}