Две суммы

Кажется слишком простым ?? Может быть.

Сегодня я решил задачу на leetcode.com, которая называется Две суммы. Однако сложность говорит о том, что это легко, для меня это было несколько сложно.

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

Пример:

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

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

Таким образом, мы несем ответственность только за работу над данной функцией с именем twoSum. Мое решение - найти индексы из отсортированного массива. Мы будем использовать два итератора с обеих сторон массива, и он прерывается, когда сумма двух итераторов равна цели.

sorted array nums: [2, 7, 11, 15] 
first iterator index fIndex: 0
second iterator index lIndex: 3
target: 18
nums[0]+nums[3]<18 so we must increase the first iterator value
fIndex = 1
nums[1]+nums[3]>18 then reduce the second iterator
lIndex = 2
nums[1] + nums[2] === 18 then we will break the loop and fIndex, lIndex must point the indices that needed to return.

Но подождите, а что, если параметр nums не отсортирован? Как бы мы ни сортировали его, он будет смешивать правильные индексы, которые будут возвращены. Таким образом, я сохранил элементы в объекте с их значениями и индексами.

initial nums                        sorted nums
[                                   [
   {val: 11, ind: 0},                  {val: 2, ind: 2},
   {val: 7, ind: 1},                   {val: 7, ind: 1},
   {val: 2, ind: 2},                   {val: 11, ind: 0},
   {val: 15, ind: 3}                   {val: 15, ind: 3}
]                                   ]

Теперь итераторы наших алгоритмов поиска, определенных выше, могут указывать на объекты, которые имеют свои начальные индексы.

Отличная работа. Реализуем функцию.

let twoSum = function(nums, target) {
    nums=nums.map(function(a,i){
                return {
                  val: a,
                  ind: i
                }
             })
             .sort(function(a,b){
                return a.val>b.val? 1:-1;
             });
    let fIndex=0, lIndex=nums.length-1;
    while(fIndex<lIndex){
        let sum = nums[fIndex].val+nums[lIndex].val;
        if(sum>target)
            lIndex--;
        else if(sum<target)
            fIndex++;
        else
            break;
    }
    return [nums[fIndex].ind, nums[lIndex].ind]
};

Это работает быстрее, чем 58 процентов отправки javascript. Надеюсь, вам понравится.