Пара элементов из заданного массива, сумма которого равна определенному целевому номеру

Я нахожусь в середине моего сеанса JavaScript. Найдите этот код в моем упражнении по кодированию. Я понимаю логику, но я не получил это условие [nums [x]].

function twoSum(nums, target_num) {  
    var map = [];  
    var indexnum = [];  

    for (var x = 0; x < nums.length; x++)  
    {  
        if (map[nums[x]] != null)  
        // what they meant by map[nums[x]]
        {  
            index = map[nums[x]];  
            indexnum[0] = index+1;  
            indexnum[1] = x+1;  
            break;  
        }  
        else  
        {  
            map[target_num - nums[x]] = x;  
        }  
    }  
    return indexnum;  
    }  
console.log(twoSum([10,20,10,40,50,60,70],50));

Я пытаюсь получить пар элементов из заданного массива, сумма которого равна определенному целевому номеру. Я написал ниже код.

function arraypair(array,sum){
        for (i = 0;i < array.length;i++) {
            var first = array[i];
            for (j = i + 1;j < array.length;j++) {
                var second = array[j];

                if ((first + second) == sum) {
            alert('First: ' + first + ' Second ' + second + ' SUM ' + sum);
            console.log('First: ' + first + ' Second ' + second);
                }
            }

        }
}

var a = [2, 4, 3, 5, 6, -2, 4, 7, 8, 9];

arraypair(a,7);

Есть ли оптимизированный способ, чем выше двух решений? Может ли кто-нибудь объяснить первое решение, что именно отображает [nums [x]] это условие указывает на?

Ответ 1

значение map, которое вы видите, является справочной таблицей, а метод twoSum реализовал то, что называется динамическим программированием

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

Давайте разберемся, как это работает, чтобы лучше понять это:

twoSum([10,20,40,50,60,70], 50)
//I removed one of the duplicate 10s to make the example simpler

В итерации 0:

значение равно 10. Наше целевое число равно 50. Когда я вижу число 10 в индексе 0, я отмечаю, что если я когда-либо найду 40 (50 - 10 = 40) в этом списке, то я могу найти его пара в индексе 0.

Таким образом, на нашей карте 40 очков к 0.

В итерации 2:

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

map[nums[x]] (то же самое, что и map[40]) вернет 0.
Это означает, что у меня есть пара для 40 с индексом 0.
0 и 2 составляют пару.

Имеет ли это смысл сейчас?

В отличие от вашего решения, где у вас есть 2 вложенных цикла, вы можете хранить ранее вычисленные значения. Это сэкономит вам время обработки, но затрачивает больше места в памяти (потому что таблица поиска будет нуждаться в памяти)

Кроме того, поскольку вы пишете это в javascript, ваша карта может быть объектом, а не массивом. Это также сделает отладку намного проще;)

Ответ 2

Используя подход HashMap с использованием временной сложности approx O (n), ниже приведен следующий код:

let twoSum = (array, sum) => {
    let hashMap = {},
      results = []

        for (let i = 0; i < array.length; i++){
            if (hashMap[array[i]]){
                results.push([hashMap[array[i]], array[i]])
            }else{
                hashMap[sum - array[i]] = array[i];
            }
          }
          return results;
    }
console.log(twoSum([10,20,10,40,50,60,70,30],50));

результат:

{[10, 40],[20, 30]}

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

Надеюсь, что это поможет.

Ответ 3

Пожалуйста, попробуйте приведенный ниже код. Он даст вам все уникальные пары, сумма которых будет равна targetSum. Он выполняет бинарный поиск, поэтому будет лучше в производительности. Временной сложностью этого решения является O (NLogN)

((arr,targetSum) => {
    if ((arr && arr.length === 0) || targetSum === undefined) {
        return false;
    } else {
        for (let x = 0; x <=arr.length -1; x++) {
            let partnerInPair = targetSum - arr[x];
            let start = x+1;
            let end = (arr.length) - 2;

             while(start <= end) {
                let mid = parseInt(((start + end)/2));
                if (arr[mid] === partnerInPair) {
                    console.log(`Pairs are ${arr[x]} and ${arr[mid]} `);
                    break;
                } else if(partnerInPair < arr[mid]) {
                    end = mid - 1;
                } else if(partnerInPair > arr[mid]) {
                    start = mid + 1;
                }
             }
        };

    };
})([0,1,2,3,4,5,6,7,8,9], 10)

Ответ 4

function twoSum(arr, S) {
 const sum = [];
  for(let i = 0; i< arr.length; i++) {
    for(let j = i+1;  j < arr.length; j++) {
      if(S == arr[i] + arr[j]) sum.push([arr[i],arr[j]])
    }
  }
 return sum
}

Грубая сила не лучший способ решить, но это работает.

Ответ 5

function twoSum(arr, target) {
    let res = [];
    let indexes = [];
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (target === arr[i] + arr[j] && !indexes.includes(i) && !indexes.includes(j)) {
                res.push([arr[i], arr[j]]);
                indexes.push(i);
                indexes.push(j);
            }
        }
    }
    return res;
}
console.log('Result - ',
    twoSum([1,2,3,4,5,6,6,6,6,6,6,6,6,6,7,8,9,10], 12)
);

Грубая сила.