Задача парных сумм

Question

У меня есть рабочий код, но я хочу улучшить понимание и реализацию различных техник кодирования в целом. Я думал, что эта проблема дает хороший шанс получить отзывы о том, что я делаю.

Идея здесь состоит в том, чтобы принять два аргумента, массив и целое число. Определите все пары в массиве, которые суммируются, чтобы получить целочисленный аргумент, а затем верните сумму индексов. Вы не можете повторно использовать индекс, и вы всегда должны использовать наименьший доступный вам индекс. Здесь есть объяснение в руководстве по кодам F CC: https://www.freecodecamp.org/learn/coding-interview-prep/algorithms/pairwise

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

Вот код:

function pairwise(arr, arg) {

  let usedIndex = [];
  let output = 0;

  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (
          arr[i] + arr[j] == arg
          && usedIndex.indexOf(i) == -1
          && usedIndex.indexOf(j) == -1
        ) { 
          usedIndex.push(i, j)
          output += i + j
      }
    }
  }

  return output;

}

pairwise([0, 0, 0, 0, 1, 1], 1) // should return 10

Answer 1

Это можно сделать за один l oop с умным использованием объекта и знанием того, что индексы можно использовать только один раз.

function pairwise(arr, arg) {
  let map = {};
  let output = 0;
  let length = arr.length;

  for (let i = 0; i < length; i++) {
    let subArr = map[arr[i]];
    if(subArr && subArr[0] !== undefined) {
      //there is an index waiting to pair, remove it and add to output
      output += subArr.pop() + i;
    } else {
      //add this index to its pair slot
      let left = arg - arr[i];
      if(!map[left]) map[left] = [];
      map[left].unshift(i);
    } 
  }

  return output;
}

console.log(pairwise([0, 0, 0, 0, 1, 1], 1), "should be 10");
console.log(pairwise([1, 4, 2, 3, 0, 5], 7), "should be 11");
console.log(pairwise([], 100), "should be 0");
console.log(pairwise([1, 3, 2, 4], 4), "should be 1");

Ключи карты представляют другое значение, необходимое для создания пары , а значения карты представляют собой массивы индексов, которые имеют значение что сделало бы пару. Индексы вставляются с использованием unshift(), так что pop() возвращает первый, который был вставлен - самый маленький.

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

Answer 2

1. Сортировать список.
2. Сделайте две фишки, идущие с концов. На каждом этапе проверяйте, подходит ли вам сумма. Если это так, захватите желаемые метри c.

Шаг 1 - O (n * logn).

Шаг 2 - O (n) - каждый счетчик будет go примерно на полпути по списку, останавливаясь при встрече.

Answer 3

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

function pairwise(arr, arg) {

  let usedIndex = [];
  let output = 0;
  let length = arr.length;

  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      if (
          arr[i] + arr[j] == arg
          && usedIndex.indexOf(i) == -1
          && usedIndex.indexOf(j) == -1
        ) { 
          usedIndex.push(i, j)
          output += i + j
      }
    }
  }
  return output;
}