04.The Exact Toll

EasyArrays
Pattern lockedSolve it, or make 3 submissions, to unlock which classic problem this story hides.
A toll plaza at night. A car waits at a red and white barrier. A tray shows four coins: 2, 7, 11 and 15. Their positions, 0 to 3, are under them. The coins 2 and 7 glow green. A green arc joins them, with the label 2 + 7 = 9. The toll board shows TOLL ₹9 and PICK 0 1.

// The story

Savita works the night shift at the Khed Shivapur toll plaza, near Pune. The plaza has one rule. Every traveller pays with exactly two tokens from their tray. The two tokens must add up to the toll exactly.

Savita numbers the tokens on a tray from 0, starting on the left. Most tokens are coins. Some are discount slips with a minus value. Two tokens on a tray can have the same value. On offer nights, the toll can be ₹0 or even less than zero. Each tray has exactly one pair that matches the toll.

A long line of trucks is waiting. Write a program that tells Savita which two positions to pick, so the gate can open.

// Your task

You get the tray nums (token values, left to right) and the toll target. Return the positions of the two tokens that add up to target.

  • Positions start at 0 for the leftmost token.
  • Every tray has exactly one correct pair.
  • Use two different tokens. You cannot use one token twice. Two different tokens can have the same value.
  • Token values can be negative or zero. The toll can also be negative or zero.

Limits: n (the number of tokens) is between 2 and 104: 2 ≤ n ≤ 104. Every token value and the toll are between -109 and 109: -109 ≤ nums[i], target ≤ 109.

Input: the first line is n. The second line has the n token values. The third line is the toll.

Output: the two positions on one line, separated by a space. Any order is fine; the checker sorts them.

Example 1:

Input:
4
2 7 11 15
9

Output:
0 1

The toll is ₹9. Token 0 is 2 and token 1 is 7. 2 + 7 = 9.

Example 2:

Input:
3
3 2 4
6

Output:
1 2

Token 0 is 3. It needs another 3, but the tray has only one 3. Tokens 1 and 2 give 2 + 4 = 6.

Example 3:

Input:
2
3 3
6

Output:
0 1

Tokens 0 and 1 are two different tokens with the same value. 3 + 3 = 6.

// Constraints

  • 2 <= nums.length <= 10000
  • -1000000000 <= nums[i] <= 1000000000
  • -1000000000 <= target <= 1000000000
  • Exactly one valid pair of distinct indices exists.

Time limit: 1s ·  Memory limit: 256 MB

Hint 1

The simplest way pairs each token with every token after it. It works, but 10,000 tokens means about 50 million tries. That is too slow.

Hint 2

Look at one token with value v. Its partner must have the value target − v. You only need to know: have you seen that value before?

Hint 3

Go through the tray once, left to right. Write each value and its position in a notebook. Before you write a token down, check the notebook for the value it needs.

solution.py
Sample tests