Find two positions whose values add up to a target, in a single pass.
What to build
An O(n) solution to a problem that looks as though it needs nested loops.
Requirements
- Read the numbers and the target
k. - Print the positions
i j, counting from 0, withi < jandjas small as possible. If severaliwork for thatj, use the smallest. - Print
NONEif there are no such positions.
Input
The first line has n and k. The second line has n whole numbers.
Output
Two numbers, or NONE.
Constraints
n is from 1 to 100000.
Example
Input:
4 9
2 7 11 15
Output:
0 1
Why it works
A dictionary of earlier values makes each lookup immediate, so one pass replaces the nested loops. Storing only the first position of each value gives the smallest i.
Examples
Example 1 · Input
4 9 2 7 11 15
Expected output
0 1
Example 2 · Input
3 100 1 2 3
Expected output
NONE
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Go through the list once, remembering where you have seen each value.
Hint 2
For each new value, look for k - value among the values already seen.
Hint 3
Keep only the first position of each value, so that i is as small as possible.
Solution
Show one correct solution (try it yourself first)
n, k = [int(x) for x in input().split()]
nums = [int(x) for x in input().split()]
seen = {}
answer = "NONE"
for j, value in enumerate(nums):
if k - value in seen:
answer = f"{seen[k - value]} {j}"
break
if value not in seen:
seen[value] = j
print(answer)