Сложность: medium
Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
Пример:
Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
👨💻 Алгоритм:
1⃣Отсортировать массив arr.
2⃣Инициализировать счетчик для количества кортежей.
Пройти по массиву тремя указателями i, j, и k:
Для каждого i, установить j на i + 1, и k на конец массива.
Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target.
3⃣Вернуть результат по модулю 10^9 + 7.
😎 Решение:
def threeSumMulti(arr, target):
arr.sort()
MOD = 10**9 + 7
count = 0
for i in range(len(arr)):
j, k = i + 1, len(arr) - 1
while j < k:
sum_ = arr[i] + arr[j] + arr[k]
if sum_ == target:
if arr[j] == arr[k]:
count += (k - j + 1) * (k - j) // 2
break
else:
left, right = 1, 1
while j + 1 < k and arr[j] == arr[j + 1]:
left += 1
j += 1
while k - 1 > j and arr[k] == arr[k - 1]:
right += 1
k -= 1
count += left * right
j += 1
k -= 1
elif sum_ < target:
j += 1
else:
k -= 1
return count % MOD
Ставь 👍 и забирай 📚 Базу знаний