Two Sum: HashMap One Pass

First thought: given that there exists exactly one solution -> use of complement (calculate and store complement value as key and index in nums array as value). To look up the complement value, time complexity minimized using HashMap (O(1) lookup time). however, this solution iterates through the nums array twice (once to populate hashmap, second to find index pairs).

My solution:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            map.putIfAbsent(target-nums[i], i);
        }
        for (int i=0; i<nums.length; i++) {
            if (map.get(nums[i])!=null && map.get(nums[i])!=i) {
                return new int[] {i, map.get(nums[i])};
            }
        }
        return new int[] {-1, -1};
    }
}

Improved Solution: same in that it uses HashMap, but only one pass needed

Map<Integer, Integer> map = new HashMap<>();
for (int i=0; i<nums.length; i++) {
	int complement = target - nums[i];
    int pairIndex = map.get(complement);
    if (pairIndex!=null) return new int[] {pairIndex, i};
    map.put(nums[i], i);
}
return null;

Catch Point:

1. 자기 자신을 볼 때, HashMap에 자기 자신은 없다 (따라서 중복 element가 사용될 가능성은 이미 거기서 rule out)
2. Array에는 "짝"이 존재하는 것이다. 달리 말해서, 짝의 두번째 element는 항상 나중에 등장하게 되어있다. 첫번째 element를 마주했을때 HashMap에 put하고, 그 다음 짝 element를 만났을때는 HashMap에서 O(1)으로 찾을 수 있다.
3. 항상 array traverse를 할 때, 한번의 traverse로 끝낼 수 있는지 확인해야 한다.