Two Sum

EasyTime 1000 msMemory 128 MB

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

You may assume there is exactly one solution, and the same element may not be used twice.

Input format

Line 1: two integers n and target (2 ≤ n ≤ 10^5, -10^9 ≤ target ≤ 10^9).
Line 2: n integers (-10^9 ≤ nums[i] ≤ 10^9), separated by spaces.

Two integers on one line: the two indices (0-based), in ascending order, separated by a space.

Exactly one valid pair is guaranteed to exist.
Think about the time and space trade-offs: the brute-force check is O(n²); a single pass with a hash map is O(n) time and O(n) space.

Example 1

Input

4 9
2 7 11 15

Output

0 1

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

Example 2

Input

3 6
3 2 4

Output

1 2

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

Example 3

Input

2 6
3 3

Output

0 1

Explanation: nums[0] + nums[1] = 3 + 3 = 6; the same index cannot be reused, two different ones can hold the same value.

Saved on this device

Loading editor…

⌘ ↵ run⌘ ⇧ ↵ submit

Input

4 9
2 7 11 15

Expected output

0 1

Run checks all 3 examples; Submit runs the hidden tests.