LeetCode 18 Вычисление расширения 2 суммы для суммы 4

Нам дан массив входных данных, и у нас есть цель. Мы хотим найти, какие два элемента в массиве образуют значение, равное целевому.

Пример:
nums= [1,2,3,4,5,6,7]
цель = 10
вывод: [[3,7], [4,6]]

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

Подход
То же, что и бинарный поиск (деление пополам), у нас есть два указателя, lptr и rptr.
lptr указывает на начальный индекс, а rptr — на последний индекс.

Теперь давайте посмотрим на представленную здесь закономерность:
Внимательно изучите эти два случая.

Случай 1.
Сохранение rptr постоянным и увеличение lptr
(1+7) → 8
(2+7) → 9
(3 +7) — —› 10
(4+7) — —› 11

Случай 2.
Сохранение lptr постоянным и увеличение rptr
(1+7) → 8
(1+6) → 7
(1 +5) → 6

Из приведенных выше двух случаев формируется шаблон, согласно которому при увеличении lptr сумма будет увеличиваться, и точно так же при увеличении rptr сумма будет уменьшаться (учитывая, что массив отсортирован).

Применение концепции
Теперь давайте применим этот подход к двум указателям, чтобы найти цель 10.
Шаг 1
Размещение lptr в индексе 0 и rptr по последнему индексу

nums = list([1,2,3,4,5,6,7])
target = 10

lptr = 0
rptr = len(nums)-1

main_ls = []

Шаг 2
Мы пройдемся по элементам

Теперь nums[lptr] + nums[rptr] = 8. Это меньше 10, что означает, что нам нужно увеличить сумму. Если увеличить сумму, то нам нужно переместить lptr.

Получается сумма 9. Снова нужно увеличить сумму.

Это сделано, получаем 10
nums[lptr] = 3 и nums[rptr] = 7. И nums[lptr]+nums[rptr]=10

Теперь нам не потребуются элементы, предшествующие lptr, и точно так же элементы, следующие за rptr. Таким образом мы увеличиваем lptr и уменьшаем rptr.

lptr += 1
rptr -= 1

Опять же, это формирует 10, и мы делаем lptr+=1 и rptr-=1.
Теперь мы видим, что lptr == rptr. Но в постановке задачи сказано, что сумма должна быть в виде двух разных элементов. Следовательно, мы прерываем итерацию.

Таким образом, вся логика такова:

while(lptr<rptr):
    two_sum =  nums[lptr]+nums[rptr]
    if  two_sum < target:
        lptr+=1
    elif two_sum > target:
        rptr-=1
    else:
        print([nums[lptr],nums[rptr]])
        lptr+=1
        rptr-=1
[3, 7]
[4, 6]

Теперь проблема в том, что если у нас есть повторяющиеся элементы в этих числах, мы не получим уникальный набор

nums = list([1,1,1,4,5,6,7,7])
target = 8

l = 0
r = len(nums)-1

main_ls = []



while(l<r):
    two_sum =  nums[l]+nums[r]
    if  two_sum < target:
        l+=1
    elif two_sum > target:
        r-=1
    else:
        print([nums[l],nums[r]])
        l+=1
        r-=1
[1, 7]
[1, 7]

Теперь, чтобы справиться с этим, мы должны увеличиваться до тех пор, пока не появятся такие повторяющиеся элементы.

Таким образом, мы сохраняем условие, что
пока nums[l] == prev и l‹r: l+=1
и таким же образом
while nums[r] == prev2 и l‹r : г-=1

Таким образом, вся логика выглядит так, а тестирование на одном случае драйвера

nums = list([1,1,1,1,7,7,7,7])
target = 8

l = 0
r = len(nums)-1

main_ls = []



while(l<r):
    two_sum =  nums[l]+nums[r]
    if  two_sum < target:
        prev = nums[l]
        while nums[l] == prev and l<r: l+=1
    elif two_sum > target:
        prev = nums[r]
        while nums[r] == prev and l<r: r-=1
    else:
        print(nums[l],nums[r])
        prev1 = nums[l]
        prev2 = nums[r]
        while nums[l] == prev1 and l<r: l+=1
        while nums[r] == prev2 and l<r: r-=1
1 7

Примечание. Это не повлияет на общую временную сложность. Остается только O(n).

Спасибо, что прочитали мою статью!!!

Директ открыт для любых вопросов!!! (https://linktr.ee/prituldave)

LeetCode 18 Вычисление расширения 2 суммы для суммы 4

Вопросы по теме