Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Idea – 1

Try each of the pairs and see if the sum equals target.

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

Runtime: 22 ms, faster than 29.76% of Java online submissions for Two Sum. Memory Usage: 38.4 MB, less than 52.20% of Java online submissions for Two Sum.

Idea – 2

For i-th element x, find target-x and see if we have already seen it in [0, i-1]. For efficient lookup we use a HashMap that stores the last index where an element was seen. Time and space . Overflow/underflow does not seem to create an issue in Java probably because the addition and subtraction behaves like being on a circle.

		int target = Integer.MIN_VALUE;
		int x = 1000;
		int y = target-x;
		int z = x+y;
		
		System.out.println( String.format( "x=%d, y=%d, z=%d", x, y, z ) );
		
		target = Integer.MAX_VALUE;
		x = -1000;
		y = target-x;
		z = x+y;
		
		System.out.println( String.format( "x=%d, y=%d, z=%d", x, y, z ) );

x=1000, y=2147482648, z=-2147483648

x=-1000, y=-2147482649, z=2147483647

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] sol = new int[2];
        HashMap<Integer, Integer> map = new HashMap();
        for(int i = 0; i < nums.length; ++i)
        {
            int delta = target-nums[i];
            if(map.containsKey(delta))
            {
                sol[0] = map.get(delta);
                sol[1] = i;
                break;
            }
            
            map.put(nums[i], i);
        }
        
        return sol;
    }
}

Runtime: 2 ms, faster than 99.73% of Java online submissions for Two Sum. Memory Usage: 38 MB, less than 84.34% of Java online submissions for Two Sum.