自己的解法, O(n * M), M是平均一个数的坐标个数

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, List<Integer>> hash = new HashMap<>();
        if (nums == null || nums.length == 0) return new int[0];

        for (int i = 0; i < nums.length; i++){
            if (!hash.containsKey(nums[i])){
                List<Integer> list = new ArrayList<>();
                list.add(i);
                hash.put(nums[i], list);
            }
            else{
                hash.get(nums[i]).add(i);
            }
        }

        int[] ans = new int[2];
        for (int i = 0; i < nums.length; i++){
            int diff = target - nums[i];
            if (hash.get(diff) != null){
                List<Integer> list = hash.get(diff);
                for (int j : list){
                    if (i != j){
                        ans[0] = i;
                        ans[1] = j;

                        return ans;
                    }
                }
            }
        }

        return ans;
    }
}

Approach #2 (Two-pass Hash Table) [Accepted]

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

Approach #3 (One-pass Hash Table) [Accepted]

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}