Problem Description

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

You may assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Example 1:

• Input: nums = [3,4,5,6], target = 7
• Output: [0,1]
• Explanation: nums[0] + nums[1] == 7, so we return [0, 1].

Example 2:

• Input: nums = [4,5,6], target = 10
• Output: [0,2]

Example 3:

• Input: nums = [5,5], target = 10
• Output: [0,1]

Constraints:

• 2 <= nums.length <= 1000
• -10,000,000 <= nums[i] <= 10,000,000
• -10,000,000 <= target <= 10,000,000
• Only one valid answer exists.

Approach

Use a HashMap to store elements and their indices as we iterate:

1. For each element, calculate the complement (target - current element)
2. Check if the complement exists in the HashMap
3. If it exists and it’s not the same index, we found our pair
4. If not, add the current element and its index to the HashMap

This approach achieves O(n) time complexity by using a hash table for O(1) lookups, avoiding the O(n²) brute force approach of checking every pair.

Solution

Initial Approach (Hashtable - Two Pass)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        Hashtable<Integer, Integer> sum = new Hashtable<>();

        for(int i=0;i<n;i++){
            sum.put(nums[i],i);
        }
        int index1 = 0;
        int index2 = 0;
        for(int i=0;i<n;i++){
            if(nums[i]+ (target-nums[i]) == target && sum.containsKey(target-nums[i]) && i!=sum.get(target-nums[i])){
                index1 = i;
                index2 = sum.get(target-nums[i]);
                break;
            }
        }

        int[] arr = new int[2];
        arr[0] = index1;
        arr[1] = index2;

        return arr;
    }
}

Optimized Approach (HashMap - Two Pass)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        HashMap<Integer, Integer> sum = new HashMap<>();

        for(int i=0;i<n;i++){
            sum.put(nums[i],i);
        }
        int index1 = 0;
        int index2 = 0;
        for(int i=0;i<n;i++){
            int x = target-nums[i];
            if(nums[i]+ (x) == target && sum.containsKey(x) && i!=sum.get(x)){
                index1 = i;
                index2 = sum.get(x);
                break;
            }
        }

        int[] arr = new int[2];
        arr[0] = index1;
        arr[1] = index2;

        return arr;
    }
}

Time Complexity: O(n)
Space Complexity: O(n)