Two Sum

EasyArray Hash Table

A billing tool is reconciling a batch of incoming payments against one invoice. nums[i] is the amount of payment i, and target is the invoice total. Exactly two of the payments together cover the invoice, and the tool needs to know which two.

Return the indices of those two payments as a two-element array, in either order.

The two indices must be different: a payment cannot be paired with itself, although two separate payments may have the same amount.
Amounts can be negative (a refund counts as a negative payment).
Every test has exactly one valid pair.

Example 1

Input: nums = [40,15,65,25], target = 80
Output: [1,2]

Explanation: Payments 1 and 2 add up to the invoice: 15 + 65 = 80. No other pair reaches 80.

Example 2

Input: nums = [-3,8,4,11], target = 1
Output: [0,2]

Explanation: The refund of -3 and the payment of 4 combine to 1.

Example 3

Input: nums = [9,6,9], target = 18
Output: [0,2]

Explanation: The two separate payments of 9 form the pair. Payment 0 on its own cannot be counted twice.

Constraints

nums holds 2 to 10^4 amounts.
Each amount, and target itself, lies between -10^9 and 10^9.
The tests always contain exactly one valid pair of indices.

💡 Hint 1

A brute-force pair check is O(n²). Can you avoid re-scanning the array?

💡 Hint 2

For each number, the partner you need is target - num. Remember what you have already seen, and where.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Walk the array once and keep a hash map from value → index of everything seen so far. For each nums[i], the number that completes the pair is target - nums[i]; if it is already in the map, you have the answer. Checking before inserting guarantees you never pair an element with itself.

Time O(n)Space O(n)

function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return [];
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer j = seen.get(target - nums[i]);
            if (j != null) return new int[] { j, i };
            seen.put(nums[i], i);
        }
        return new int[0];
    }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function twoSum(nums, target) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit