题目描述

难度分:$1500$

输入$n(1 \leq n \leq 3 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

把$a$划分成尽量多的段，使得每一段都有重复数字。

如果无法做到，输出$-1$。

否则，输出的第一行是段数$k$，然后输出$k$行，表示每一段的开始和结束下标（下标从$1$开始）。

可以按任意顺序输出这些段。

输入样例$1$

5
1 2 3 4 1

输出样例$1$

1
1 5

输入样例$2$

5
1 2 3 4 5

输出样例$2$

-1

输入样例$3$

7
1 2 1 3 1 2 1

输出样例$3$

2
1 3
4 7

算法

贪心

初始化$left=1$，用一个$right$指针遍历数组$a$，同时用一个哈希表$counter$统计扫过的元素频数。一旦发现$counter[a[right]] \gt 1$，就让$right$位置作为一个段的右端点，将$(left,right)$存入一个$intervals$数组，更新$left=right+1$，然后清空$counter$扫描后面的元素找下一个段。

注意最后一个子段可能始终都没有发现重复元素，当遇到这种情况时，将最后一个子段融入到倒数第二段中即可。

复杂度分析

时间复杂度

遍历一遍$a$数组就可以得到所有子数组的左右端点，时间复杂度是线性的，为$O(n)$。

空间复杂度

空间瓶颈在于需要一个$intervals$数组存储所有子段的端点，这个数组的规模是$O(n)$的，哈希表$counter$在最差情况下也会存$O(n)$级别数量的元素。因此，额外空间复杂度也为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <chrono>
#include <unordered_map>
#include <vector>

using namespace std;
const int N = 300010;
int n, a[N];

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
      x += 0x9e3779b97f4a7c15;
      x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
      x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
      return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
      static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
      return splitmix64(x + FIXED_RANDOM);
  }
};

int main() {
    scanf("%d", &n);
    vector<pair<int, int>> intervals;
    unordered_map<int, int, custom_hash> counter;
    int pre = 1;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        counter[a[i]]++;
        if(counter[a[i]] > 1) {
            intervals.push_back({pre, i});
            pre = i + 1;
            counter.clear();
        }
    }
    if(intervals.empty()) {
        puts("-1");
        exit(0);
    }
    int mx = 0;
    for(auto&[k, v]: counter) {
        mx = max(mx, v);
    }
    if(mx == 1) {
        intervals.back().second = n;
    }else {
        if(pre + 1 <= n) intervals.push_back({pre, n});
    }
    printf("%d\n", (int)intervals.size());
    for(auto&interval: intervals) {
        printf("%d %d\n", interval.first, interval.second);
    }
    return 0;
}