Two Sum Problem

Given an array A and an integer target, find the indices of the two numbers in the array whose sum is equal to the given target.

Note: The problem has exactly one solution. Do not use the same element twice.

Example

A: [1, 3, 3, 4]
target: 5
Answer: [0, 3]

Constraints

1 <= T <= 10
2 <= n <= 105
-10 power 9<= Ai <= 10 power 9
-10 power 9<= target <= 10 power 9

Solution 1

time complexity n*log(n)

class Solution {
	int[] twoSum(int[] A, int target) {
	    // add your logic here
		Pair[] pair = new Pair[A.length];
		for(int i=0;i<A.length;i++){
			Pair p = new Pair(A[i],i);
			pair[i] = p;
		}
		
		Arrays.sort(pair, new Comparator<Pair>(){
			@Override
			public int compare(Pair p1, Pair p2){
				return p1.value-p2.value;
			}
		});
		
		int i=0;
		int j=A.length-1;
		while(i<j){
			long value = pair[i].value + pair[j].value;
			if(value==(long)target){
				int [] ans = new int[2];
				ans[0] = pair[i].index;
				ans[1] = pair[j].index;
				return ans;
			}else if(value<target){
				i++;
			}else{
				j--;
			}
		}
		return null;
	}
}

class Pair{
	int value;
	int index;
	
	public Pair(int value, int index){
		this.value = value;
		this.index = index;
	}
}