Two Sum

The trick here is to traverse the array and push the difference between the target and number from array into a hashmap. The difference calculated should be stored as key and the original number from array as the value. We need to continue traversing until we hit a number which is one of the keys in the hashmap or until we exhaust all numbers in the array. If we find a match, the key-value pair is the required pair which sums to the target number. Since we are only traversing the array once at most, the time complexity will be O(n).

public class TwoSum{
    public List findTwoSum(int[] numArr, int target){
        List<Integer> retList = new ArrayList<>();
        if(numArr == null || numArr.length < 2) return retList;
        Map<Integer, Integer> numMap = new HashMap<>();
        for(int num: numArr){
            //check if number present in map
            if(numMap.containsKey(num)){
                retList.add(numMap.get(num));
                retList.add(num);
                return retList;
            }
            //Push difference between target and number to map
            numMap.put(num, target-num);
        }
        return retList;
    }
}

Execute solution @jdoodle