Solutions for LeetCode “Two Sum” problem in Java

Leetcode Problem:- https://leetcode.com/problems/two-sum/

Let’s start understand the problem,

Here, we have to find the indices of two numbers from given array in which sum of that two number should be equal to target number that given in function argument.

Here, I thought, easiest solution is we have to just find numbers whose sum is equal to target number. So, first idea click on my brain is:

target number = first number + second number

but here problem is that numbers could be from any indices. So, second idea strike to my brain is:

target number = array[i] + array[j]

class Solution {
    public int[] twoSum(int[] nums, int target) {
         
        
        for(int i=0;i<nums.length;i++)
        {
            for(int j=0;j<nums.length;j++)
            {
            
                if(i == j)
                {
                    break; 
                }
              
                if(nums[i] + nums[j] == target)
                {
                    return new int[] {i,j};
                }
            }    
        }
        return new int[] {0,0};    
    }
}

Here, my simple logic is if we got i == j(same value) then simply break that loop. And rest element should be go as per our logic(target = array[i]+array[j]) and return two indices that match our logic.

But, here problem is the complexity of this program is O(n²).We need to reduced that complexity.

So, I used Hashmap to reduce the complexity.

import java.util.HashMap;
class Solution {
    public int[] twoSum(int[] nums, int target) {
         
        HashMap <Integer, Integer> map 
                       = new HashMap<Integer, Integer>();
        
        for(int i=0;i<nums.length;i++)
        {
                if(map.containsKey(target - nums[i]))
                {
                    return new int[] {i,map.get(target-nums[i])};
                }
            
                map.put(nums[i], i);
     
        }
        throw new IllegalArgumentException("Nothing");
         
    }
}

Here is the performance of second code.

Hit here one clap if you like my solving approach and solution.

Thanks for your patiently read !!!