Рефакторинг, вложенный в цикл

Question

Инструкции

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

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

Пример

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Как я могу реорганизовать это, чтобы устранить вложенные в-л oop? Я бы хотел уменьшить сложность времени.

Код

const twoSum = function(nums, target) {
    for(let i in nums){
      for(let j in nums) {
        if(nums[i] + nums[j] === target && nums[i] != nums[j]) {
            return [i, j];
        }
      }
    }
};

console.log(twoSum([2, 7, 11, 15], 9));

Answer 1

Вы можете решить эту проблему со временем O(n). При таком подходе необходимо решить, что массив должен быть отсортирован.

let twosum = (arr, x) => {
  let s = 0,
    e = arr.length - 1;
  let loc = [];

  while (s < e) {
    if (arr[s] + arr[e] === x) {
      loc.push([s,e]);
      s++;
      e--;
    } else if (arr[s] + arr[e] < x) {
      s++;
    } else {
      e--;
    }
  }

  return loc;
};

console.log(twosum([1, 2, 3, 4, 5, 7, 8], 9));
console.log(twosum([2, 7, 11, 15], 9));

Алгоритм этого, если кому-то интересно:

1.   Set s value as 0
2.   Set e value as last index say (arr.length - 1)
3.   While s is less than e i.e not pass one another
4.   Check if arr[s] + arr[e] === x then we find it.
4.1. increment s value by 1 as there is no possibility to find any combination before the current s value
4.2. decrement e value by 1 as there is no possibility to find any combination after the current e value
4.3. collect the indexes where the match found.
5.   If arr[s] + arr[e] < x
5.1  increment s as there is no possibility to find any combination before the current s value. But there still has the possibility for the e value to get a match.
6.   If arr[s] + arr[e] > x
6.1  decrement e as there is no possibility to find any combination after the current e value. But there still has the possibility for the s value to get a match.

Answer 2

Поскольку это, кажется, домашняя работа, я сделаю пару предложений, не выдавая полного решения:

• Ваш текущий код повторяет проверки индекса. Например, вы перебираете индексы [0,1] и [1,0], которые всегда будут иметь одинаковую сумму, поскольку a + b = b + a. Вместо этого я бы предложил ваш l oop для i go от 0 до len-1, а ваш l oop для j go от i + 1 до len-1. Таким образом, вы никогда не будете дублировать проверки.
• Часть вашей текущей проверки включает условие nums[i] != nums[j], но ваша проблема не утверждает, что два значения в массиве не могут быть одинаковыми. Можно ли вызвать эту функцию со значениями типа toSum([1, 4, 4], 8), такими, что 4 + 4 = 8? Если это так, то вы можете снять проверку nums[i] != nums[j], чтобы сэкономить время.
• Не ясно, отсортирован ли предоставленный массив. Если это не так, то вы можете создать переменную отслеживания для учета уже проверенных значений и запретить проверку их на будущих итерациях. Например, если вы уже сравнили значение 4 со всеми другими значениями в массиве и не нашли решения, то, если вы встретите 4 позже в массиве, нет смысла проверять его.

Answer 3

Можно сохранить разницу каждого элемента с целью внутри объекта с результатом в качестве ключей и индексом в качестве значений. Это сделает проверку существования элемента внутри объекта без зацикливания всего содержимого. В другом l oop проверьте, существуют ли элементы массива в объекте, если они есть, то у вас есть пара. Дополнительным условием является предотвращение сравнения элемента с самим собой.

const twoSum = function(nums, target) {  
  const temp = {};
  for(let i=0; i<nums.length; i++) {
    temp[target - nums[i]] = i;
  }

  for(let i=0; i<nums.length-1; i++) {
    if(temp[nums[i]] && temp[nums[i]] !== i) {
      return [i, temp[nums[i]]]
    }
  }
};

console.log(twoSum([2, 11, 7, 17], 9));
console.log(twoSum([1, 3, 4, 2], 6));