java代码在编写FirstDuplicate方法时会遇到时间限制问题

Question

我试图通过代码战解决下面的问题。问题结束后，我用Java留下了答案。该代码适用于所有问题，但最后一个问题除外。报告了时限异常。我该怎么做才能使其运行在3000毫秒以下（代码要求）

Note: Write a solution with O(n) time complexity and O(1) additional space complexity, since this is what you would be asked to do during a real interview.

给定仅包含1到a.length范围内的数字的数组a，查找第二次出现的索引最小的第一个重复数字。换句话说，如果有多个重复的数字，则返回第二个数字的索引小于第二个数字的索引的数字。如果没有这样的元素，则返回-1

范例

对于a=[2,3,3,1,5,2]，输出应该是 第一次重复（a）=3

有两个重复：数字2和3。第二次出现的3的指数比第二次出现的2的指数小，所以答案是3

对于a=[2,4,3,5,1]，输出应该是 第一次重复（a）=-1

输入/输出

[时限]3000毫秒（爪哇） [input]数组。整数a

保证约束条件： 1.≤ a、 长度≤ 105, 1.≤ a[i]≤ a、 长度

[输出]整数

数组中多次出现在数组中且第二次出现时具有最小索引的元素。如果没有这样的元素，则返回-1

    int storedLeastValue = -1;
    int indexDistances = Integer.MAX_VALUE;
    int indexPosition = Integer.MAX_VALUE;

    for (int i = 0; i < a.length; i++) 
    {   
            int tempValue = a[i];

            for (int j = i+1; j < a.length; j++) {
                if(tempValue == a[j])
                {
                    if(Math.abs(i-j) < indexDistances && 
                      j < indexPosition)
                    {
                        storedLeastValue = tempValue;
                        indexDistances = Math.abs(i-j);
                        indexPosition = j;
                        break;
                    }
                }
            }
        }

        return storedLeastValue;

Answer 1

接受的答案与任务不匹配。 如果输入数组确实包含的值不大于其长度，那么它就可以工作。 但确实如此，例如：[5,5]

所以，我们必须定义哪个数字最大

int firstDuplicate(int[] a) {

    int size = 0;
    for(int i = 0; i < a.length; i++) {
        if(a[i] > size) {
            size = a[i];
        }
    }

    int[] t = new int[size+1];

    for(int i = 0; i < a.length; i++) {
        if(t[a[i]] == 0) {
            t[a[i]]++;
        } else {
            return a[i];
        }
    }
    return -1;
}