Найти пару элементов из данного массива, сумма которых равна заданному c целевому числу в JavaScript

Question

В Javascript есть какой-нибудь другой эффективный способ решения этой задачи?

Я пробовал как:

const a1 = [1,3,4,2,5,7,8,6];
var newArray =[];

function fun(a,n){      

for(let i = 0; i<a.length; i++){
 for(let j=i+1; j<a.length; j++){        
   if((a[i]+a[j])==n){        
     newArray.push([a[i],a[j]]);       
    }
  }
 }
}     

fun(a1, 10)
console.log(newArray);

Вот вывод:

[(3,7),(4,6),(2,8)]

Answer 1

Я думаю, что ваш метод имеет смысл с точки зрения грубой силы.

С точки зрения оптимизации, на ум приходит несколько вещей.

1. Подсчет дубликатов? Если нет, вы можете удалить все дубликаты из стартовых списков.

2. Вы можете отсортировать списки в порядке возрастания и пропустить остаток внутреннего l oop, когда сумма превышает целевое значение.

Answer 2

Это общая проблема программирования, обычно называемая «проблемой двух сумм», которая сама является подмножеством проблемы подмножества сумм . Но тем не менее можно решить эффективно, и я использовал эту статью в качестве вдохновения.

const a1 = [1, 3, 4, 2, 5, 7, 8, 6];

// our two sum function which will return
// all pairs in the array that sum up to S
function twoSum(arr, S) {

  const sums = [];
  const hashMap = new Map();

  // check each element in array
  for (let i = 0; i < arr.length; i++) {

    // calculate S - current element
    let sumMinusElement = S - arr[i];

    // check if this number exists in hash map
    // if so then we found a pair of numbers that sum to S
    if (hashMap.has(sumMinusElement.toString())) {
      sums.push([arr[i], sumMinusElement]);
    }

    // add the current number to the hash map
    hashMap.set(arr[i].toString(), arr[i])
  }

  // return all pairs of integers that sum to S
  return sums;
}

console.log(twoSum(a1, 10))

Здесь я использую объект Map , так как я думаю, что это быстрее, когда проверяется, существует ли уже число, но я могу ошибаться, и вы можете использовать только простой объект, как в статье, если хотите.

Answer 3

Вопрос помечен javascript, но этот ответ в основном зависит от языка c.

Если массив отсортирован (или вы можете его отсортировать), вы можете перебирать массив и для каждого элемент x в нем двоичный поиск (target-x) в массиве. Это дает вам время выполнения O (nlogn).

Если вы можете использовать дополнительную память, вы можете заполнить словарь элементами массива, а затем для каждого элемента x в массиве найдите словарь для (мишень-х). Если ваш словарь реализован в хеш-таблице, это дает вам время выполнения O (n).