Two Sum

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Approach:

Instead of checking all pairs, we can use a hash map (dictionary in Python) to keep track of the numbers we have already visited and their corresponding indices. This allows us to find the solution in a single pass through the array.

Initialize a Hash Map: Create an empty hash map (or dictionary) that will store the numbers we’ve seen so far as keys and their indices as values.

Iterate Through the List: Loop through the list, and for each number:

• Calculate the difference (target - current_number).
• Check if this difference exists in the hash map.
  • If it does, that means we found the pair of numbers that sum to the target, and we return their indices (the current index and the index of the number from the hash map).
  • If it doesn’t, store the current number and its index in the hash map for future reference.

Return the Indices: As soon as a pair is found, return the indices. Since there’s exactly one solution, no need to continue the loop.

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

        for (int i = 0; i < nums.length; i++){
            int num = nums[i];

            int diff = target - num;

            if (hashMap.containsKey(diff)){
                return new int[] {hashMap.get(diff), i};
            }
            hashMap.put(num,i);
        }
        return new int[] {};
    }
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i