前后缀预处理|二分

lc3488

前后各加一个哨兵 解决边界情况

hash分组后 二分query

class Solution {
public:
vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
unordered_map<int, vector<int>> indices;
for (int i = 0; i < nums.size(); i++)
indices[nums[i]].push_back(i);

int n = nums.size();
for (auto& [_, p] : indices) {
// 前后各加一个哨兵
int i0 = p[0];
p.insert(p.begin(), p.back() - n);
p.push_back(i0 + n);
}

for (int& i : queries) { // 注意这里是引用
auto& p = indices[nums[i]];
if (p.size() == 3) {
i = -1;
} else {
int j = ranges::lower_bound(p, i) - p.begin(); //找到此位置后 取最小
i = min(i - p[j - 1], p[j + 1] - i);
}
}
return queries;
}
};

前后缀 预处理记录 o n

class Solution {
public:
vector<int> solveQueries(vector<int>& nums, vector<int>& queries)

{
int n = nums.size();
vector<int> left(n), right(n);
unordered_map<int, int> pos;
for (int i = -n; i < n; i++) {
if (i >= 0) {
int j = pos[nums[i]];
left[i] = j;
// 对于左边的 j 来说，它的 right 就是 i
if (j >= 0) {
right[j] = i;
} else {
right[j + n] = i + n;
}
}
pos[nums[(i + n) % n]] = i;
}

for (int& i : queries) {
int l = left[i];
i = i - l == n ? -1 :min(i - l, right[i] - i);
}
return queries;
}
};