Given an array of integers
The program should return indices of the two numbers such that they add up to the target, where
Put both these numbers in order in an array and return the array from your function. Note that, if no pair exists, return an empty list.
If multiple solutions exist, output the one where
Solution
There are many solutions to the problem.
Solution 1: Sorting Based
Time Complexity : O(nlogn)
Space Complexity : O(1)
Solution 2: Hashing Based
With hashing, we can get a linear time complexity solution.Time Complexity : O(n)
Space Complexity : O(n)
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
import java.util.*; public class TwoSumZero { public static void main(String[] args) { Integer [] a= { 2, 7, 11, 15 }; System.out.println(new TwoSumZero().twoSum(Arrays.asList(a), 9)); } public ArrayList<Integer> twoSum(final List<Integer> A, int B) { ArrayList<Integer> result=new ArrayList<Integer>(); //result list for index1 and index2 Map<Integer,Integer> map=new HashMap<Integer,Integer>(); if(A.size()<2) return result; for(int i=0;i<A.size();i++){ if(map.containsKey(A.get(i))){ // Check if number is already present in Map result.add(map.get(A.get(i))); //Get index1 from Map entry value. result.add(i+1); //Current index will be index2 break; } if(!map.containsKey(B-A.get(i)))map.put(B-A.get(i),i+1); //Insert new entry } return result; } } |
Output
We acknowledge you to write a comment if you have a better solution or having any doubt on the above topic.