Editorial for Two Sum
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Approach
Scan left to right while storing previously seen values in a hashmap:
- At index
j, the needed partner value istarget - a[j]. - If that value is already in the hashmap at index
i, outputi + 1andj + 1. - Otherwise, store
a[j]with its index and continue.
Because each lookup and insert is on average, total time complexity is
.
Solution (Python)
n, target = (int(x) for x in input().split())
a = [int(x) for x in input().split()]
seen: dict[int, int] = {}
for i in range(n):
need = target - a[i]
if need in seen:
print(seen[need] + 1, i + 1)
break
seen[a[i]] = i
Comments