3. Two Sum

Difficulty: easy · Array, Hash Table

Problem

Given an array of integers `nums` and an integer `target`, find the two **different** indices `i` and `j` such that `nums[i] + nums[j] == target`. Exactly one such pair exists. Print the two indices, 0-based, smaller first.

Input

The first line holds `n`. The second holds `n` integers, `nums`. The third holds `target`.

Output

Print `i j` with `i < j`.

Example 1

Input:
4
2 7 11 15
9
Output:
0 1

Explanation: nums[0] + nums[1] = 2 + 7 = 9.

Example 2

Input:
3
3 2 4
6
Output:
1 2

Explanation: nums[1] + nums[2] = 2 + 4 = 6.

Example 3

Input:
2
3 3
6
Output:
0 1

Explanation: nums[0] + nums[1] = 3 + 3 = 6.

Example 4

Input:
5
-1 -2 -3 -4 -5
-8
Output:
2 4

Explanation: nums[2] + nums[4] = -3 + -5 = -8.

Example 5

Input:
4
0 4 3 0
0
Output:
0 3

Explanation: nums[0] + nums[3] = 0 + 0 = 0.

Example 6

Input:
6
1 5 9 13 17 21
38
Output:
4 5

Explanation: nums[4] + nums[5] = 17 + 21 = 38.

Example 7

Input:
3
1000000000 -1000000000 5
0
Output:
0 1

Explanation: nums[0] + nums[1] = 1000000000 + -1000000000 = 0.

Example 8

Input:
6
-23 29 4 -12 23 -19
-8
Output:
2 3

Explanation: nums[2] + nums[3] = 4 + -12 = -8.

Example 9

Input:
6
-6 -3 17 -16 -23 16
-39
Output:
3 4

Explanation: nums[3] + nums[4] = -16 + -23 = -39.

Example 10

Input:
5
-5 -18 15 -22 26
8
Output:
1 4

Explanation: nums[1] + nums[4] = -18 + 26 = 8.

Constraints

- 2 <= n <= 10^4 - -10^9 <= nums[i], target <= 10^9 - Exactly one valid pair exists.

Solutions are judged against 10 sample and 5 hidden tests. Sign in to solve it · All problems