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.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

There are different types of approach to this
1) Brute Force Approach

you can use two nested loops to check all pairs of numbers to see if they add up to the target. This approach has a time complexity of O(n^2) because you're checking all possible pairs.

for(int i=0;i<nums.length-1;i++){
    for(int j=i+1;j<nums.length;j++){
        if(target==nums[i]+nums[j])
            return new int[]{i, j};
    }
}

Example 1:

2)optimize Approach

A more efficient approach is to use a hash table (JavaScript object) to store the numbers you have seen so far and their indices. This allows you to find the complement of each number in O(1) time.

Example 1:

int arr[]=new int[]{2,9,5,7};
        int target=9;
        int n=arr.length;
        HashMap<Integer,Integer> container=new HashMap<>();
        for(int i=0;i<n;i++){
            int num=target-arr[i];
            if(container.containsKey(num)){
                System.out.println("first index "+container.get(num)+" second index "+i);
            }
            container.put(arr[i],i);
        }