Как назначить переменную уникальным способом для дополнения в вычитании - PullRequest
Новая
       12

Как назначить переменную уникальным способом для дополнения в вычитании

0 голосов
/ 25 июня 2019

Я пытаюсь присвоить переменную "дополнение" так, чтобы выражение Math.abs(array[i]-complement)==diff было истинным, но я не совсем понимаю, как это реализовать.Я подумал о том, чтобы попытаться использовать условные выражения, если array[i] больше diff, то что произойдет с complement, но эти условия не всегда верны во всех случаях.Может ли кто-нибудь подсказать мне, возможно ли это или нет, и если нет, что мне делать?

По сути, я пытаюсь найти, сколько путей в массиве существует пара, где их разность равнаопределенное число (переменная diff), и я хочу найти «дополнение», чтобы я мог быстро найти в хэш-таблице O (N) сложность времени.

1 Ответ

0 голосов
/ 25 июня 2019

Это в основном проблема 2-diff.

Я могу записать psuedocode, но реализация зависит от вас!

Предисловие

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

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

Psuedocode 

let nums be our array of numbers
let diff be our difference
let hash be a hashtable under SUHA

for each num in nums:
    if (num in hash):
        (num, hash[num]) is our pair!
    let c1 = num + diff
    let c2 = num - diff

    hash[c1] = num
    hash[c2] = num

Вот и все!

Интуиция

Хеш-карта хранит все дополнения чисел, поэтому, когда мы смотрим на хеш-карту, мы в основном спрашиваем: «Является ли это число дополнением к другому числу, которое мы уже видели?»

...