目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

题目描述

小华和小薇一起通过玩积木游戏学习数学。
他们有很多积木，每个积木块上都有一个数字，积木块上的数字可能相同。
小华随机拿一些积木挨着排成一排，请小薇找到这排积木中数字相同且所处位置最远的2块积木块，计算他们的距离，小薇请你帮忙替她解决这个问题。

输入描述

第一行输入为N，表示小华排成一排的积木总数。
接下来N行每行一个数字，表示小华排成一排的积木上数字。

输出描述

相同数字的积木的位置最远距离；如果所有积木数字都不相同，请返回-1。

备注

• 0<=积木上的数字<10^9
• 1<=积木长度<=10^5

用例

题目解析

这题第一眼看上去好像是要用双指针做，但是实操起来却不行。

这题的数组长度会达到10^5，因此时间复杂度要至少控制在O(n)。

我的解题思路如下：

定义一个idx对象，用于存放每个num出现的索引位置，num作为idx对象属性，num出现的索引位置作为idx[num]的数组的元素。

然后遍历nums数组（即从第二行开始输入的数的集合），开始录入num的索引位置到idx对象中。

统计完后，开始遍历idx对象属性，即每个num，然后先判断idx[num]的数组长度是否大于1，若不大于，则不考虑，若大于，则用idx[num]数组的最后一个索引位置 减去 idx[num]数组的第一个索引位置。按照上面逻辑，计算出最大的索引差作为题解。

若没有符合要求的，则返回-1。

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
let n;
rl.on("line", (line) => {lines.push(line);if (lines.length === 1) {n = lines[0] - 0;}if (n && lines.length === n + 1) {lines.shift();const arr = lines.map(Number);console.log(getResult(arr));lines.length = 0;}
});function getResult(nums) {const idx = {};for (let i = 0; i < nums.length; i++) {const num = nums[i];idx[num] ? idx[num].push(i) : (idx[num] = [i]);}let ans = -1;for (let k in idx) {if (idx[k].length > 1) {ans = Math.max(ans, idx[k].at(-1) - idx[k][0]);}}return ans;
}