找到给定数组中距离最长的元素,其中每个元素出现两次？

Question

给定一个int数组,每个int在数组中恰好出现TWICE.找到并返回int,使得这对int在此数组中具有彼此之间的最大距离.

例如 [2, 1, 1, 3, 2, 3]

2: d = 5-1 = 4;
1: d = 3-2 = 1;
3: d = 6-4 = 2;
return 2

我的想法:

使用hashmap,key是a[i],value是索引.扫描a[],将每个数字放入哈希值.如果数字被命中两次,请使用其索引减去旧数字索引,并使用结果更新哈希中的元素值.

之后,扫描哈希并返回具有最大元素(距离)的密钥.在时间和空间上都是O(n).

如何在O(n)时间和O(1)空间中进行？

Answer 1

您希望拥有最大距离，因此我假设您搜索的数字更有可能位于开始和结束处。这就是为什么我会同时从开始和结束循环数组。

[2, 1, 1, 3, 2, 3]
Check if 2 == 3?
Store a map of numbers and position: [2 => 1, 3 => 6]
Check if 1 or 2 is in [2 => 1, 3 => 6] ?

我知道，这甚至不是伪代码，也不完整，只是为了给出这个想法。