题解 | #【模板】双指针#

题目链接

【模板】双指针

题目描述

给定一个长度为 $n$ 的数组 $a$ ，请找出所有最长的连续区间，要求区间中的元素两两不同。

输入:

第一行输入一个整数 $n$ ，代表数组元素的数量。
第二行输入 $n$ 个整数，代表数组 $a$ 。

输出:

第一行输出一个整数，代表满足条件的最长区间的数量。
接下来若干行，每行输出两个整数 $l$ 和 $r$ ，代表一个满足条件的区间的起始和结束下标（1-based）。
请按照区间起始下标 $l$ 的升序输出所有结果。

解题思路

本题旨在寻找所有最长的、不包含重复元素的连续子数组。这是一个经典问题，可以使用双指针（也称为滑动窗口）的方法来高效解决。

我们使用一左一右两个指针， $l$ 和 $r$ ，来维护一个动态的窗口 $[l, r]$ 。我们还需要一个数据结构（如哈希表）来实时记录窗口内各元素的出现次数。

算法步骤如下：

初始化左指针 $l=0$ ，最大长度 $max\_len = 0$ ，并用一个列表 results 存储所有最长区间的左右端点。我们还需要一个哈希表 counts 来存储窗口内元素的频率。
用右指针 $r$ 从 $0$ 到 $n-1$ 遍历整个数组，代表窗口的右边界不断向右扩张。 a. 将新元素 $a[r]$ 加入窗口，并在 counts 中增加其计数。 b. 收缩窗口：检查 $a[r]$ 的计数。如果大于 1，说明窗口内出现了重复元素。此时，我们需要不断地将左指针 $l$ 向右移动，并更新 counts 中对应元素的计数，直到 $a[r]$ 的计数恢复为 1。 c. 更新结果：在确保窗口 $[l, r]$ 内没有重复元素后，计算当前窗口的长度 current_len = r - l + 1。 i. 如果 current_len > max_len，说明我们找到了一个新的更长的无重复区间。此时，更新 $max\_len = \text{current\_len}$ ，清空 results 列表，并将当前区间 $(l+1, r+1)$ 加入。 ii. 如果 current_len == max_len，说明我们找到了一个与当前最长长度相等的无重复区间。直接将当前区间 $(l+1, r+1)$ 加入 results 即可。
遍历结束后，results 中就保存了所有最长的无重复元素区间。按要求输出即可。

由于两个指针 $l$ 和 $r$ 都只会从左到右单向移动最多 $n$ 次，所以该算法的时间复杂度为 $\mathcal{O}(n)$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    map<int, int> counts;
    vector<pair<int, int>> results;
    int max_len = 0;
    int l = 0;

    for (int r = 0; r < n; ++r) {
        counts[a[r]]++;
        
        // 当窗口内出现重复时，收缩左边界
        while (counts[a[r]] > 1) {
            counts[a[l]]--;
            if (counts[a[l]] == 0) {
                counts.erase(a[l]);
            }
            l++;
        }

        int current_len = r - l + 1;
        if (current_len > max_len) {
            max_len = current_len;
            results.clear();
            results.push_back({l + 1, r + 1});
        } else if (current_len == max_len) {
            results.push_back({l + 1, r + 1});
        }
    }

    cout << results.size() << endl;
    for (const auto& p : results) {
        cout << p.first << " " << p.second << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        Map<Integer, Integer> counts = new HashMap<>();
        List<int[]> results = new ArrayList<>();
        int maxLen = 0;
        int l = 0;

        for (int r = 0; r < n; r++) {
            counts.put(a[r], counts.getOrDefault(a[r], 0) + 1);

            // 当窗口内出现重复时，收缩左边界
            while (counts.get(a[r]) > 1) {
                counts.put(a[l], counts.get(a[l]) - 1);
                if (counts.get(a[l]) == 0) {
                    counts.remove(a[l]);
                }
                l++;
            }

            int currentLen = r - l + 1;
            if (currentLen > maxLen) {
                maxLen = currentLen;
                results.clear();
                results.add(new int[]{l + 1, r + 1});
            } else if (currentLen == maxLen) {
                results.add(new int[]{l + 1, r + 1});
            }
        }

        System.out.println(results.size());
        for (int[] p : results) {
            System.out.println(p[0] + " " + p[1]);
        }
    }
}

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))

counts = defaultdict(int)
results = []
max_len = 0
l = 0

for r in range(n):
    counts[a[r]] += 1
    
    # 当窗口内出现重复时，收缩左边界
    while counts[a[r]] > 1:
        counts[a[l]] -= 1
        if counts[a[l]] == 0:
            del counts[a[l]]
        l += 1
        
    current_len = r - l + 1
    if current_len > max_len:
        max_len = current_len
        results = [(l + 1, r + 1)]
    elif current_len == max_len:
        results.append((l + 1, r + 1))

print(len(results))
for l_res, r_res in results:
    print(l_res, r_res)

算法及复杂度

算法：双指针 / 滑动窗口
时间复杂度： $\mathcal{O}(n)$ 。左右指针都只遍历数组一次，哈希表操作的均摊时间复杂度为 $\mathcal{O}(1)$ 。
空间复杂度： $\mathcal{O}(k)$ ，其中 $k$ 是数组中不同元素的数量。在最坏情况下，所有元素都不同， $k$ 等于 $n$ ，所以空间复杂度为 $\mathcal{O}(n)$ 。空间主要用于哈希表和结果列表。