All DSA problems
EasyArraysGoogleAmazonMeta

Two Sum

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 each input has **exactly one solution**, and you may not use the same element twice.

Print the two indices (smaller index first) separated by a space.

Examples

Example 1

Input:

4
2 7 11 15
9

Output: 0 1

nums[0] + nums[1] = 2 + 7 = 9

Example 2

Input:

3
3 2 4
6

Output: 1 2

nums[1] + nums[2] = 2 + 4 = 6

Constraints

  • 2 ≤ n ≤ 10^4
  • -10^9 ≤ nums[i], target ≤ 10^9
  • Exactly one valid answer exists

Target: O(n) time · O(n) space