// T(n) = O(n)，S(n) = O(n)
// 时间复杂度系数为1，比参考答案的2略有提高

class Solution {
    public int duplicateInArray(int[] nums) {
        Map<Integer, Integer> numsMap = new HashMap<>();
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 || nums[i] > nums.length - 1) {
                return -1;
            } else if (numsMap.containsKey(nums[i])) {
                index = i;
            } else {
                numsMap.put(nums[i], 1);
            }
        }
        return index == -1 ? -1 : nums[index];
    }
}