题目链接

【模板】双指针

题目描述

给定一个长度为 的数组，找出其中所有最长的、元素两两不同的连续子区间。

解题思路

这个问题要求我们找到所有最长的、不包含重复元素的子数组。这是一个典型的可以使用**双指针（滑动窗口）**技巧解决的问题。

我们使用两个指针， 和 ，来维护一个动态的、始终满足“元素两两不同”这一性质的窗口 。同时，我们还需要一个数据结构（如哈希表）来快速判断窗口内是否存在某个元素。

算法步骤如下：

  1. 初始化：

    • , 。
    • 用于记录最长无重复子区间的长度。
    • 列表用于存储所有最长区间的端点。
    • 哈希表用于记录当前窗口内各元素的出现次数。

  2. 扩展窗口：

    • 指针不断向右移动，将新元素 纳入窗口。
    • 每纳入一个新元素，就将其在 中的计数加 1。

  3. 收缩窗口：

    • 如果在加入 后，发现 ，这说明窗口内出现了重复元素。
    • 此时，我们需要从左侧收缩窗口，即不断将 指针右移，并更新 ，直到 的计数恢复为 1。

  4. 更新结果：

    • 在每一次 指针移动后（并完成了必要的收缩），窗口 都是一个有效的无重复子区间。
    • 计算当前窗口长度 。
    • 如果 ：说明我们找到了一个新的、更长的无重复子区间。此时，更新 ，清空 列表，并将当前区间 （题目要求 1-based 索引）加入。
    • 如果 ：说明我们找到了一个与当前最长长度相同的无重复子区间。此时，只需将当前区间 加入 即可。

  5. 输出：

    • 遍历完整个数组后， 中就存放了所有最长的无重复子区间。按照题目要求输出即可。由于我们的遍历是从左到右进行的，结果自然是按起始位置升序排列的。

代码

#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> window_counts;
    vector<pair<int, int>> result_intervals;
    int max_len = 0;
    int left = 0;

    for (int right = 0; right < n; ++right) {
        window_counts[a[right]]++;

        while (window_counts[a[right]] > 1) {
            window_counts[a[left]]--;
            left++;
        }

        int current_len = right - left + 1;
        if (current_len > max_len) {
            max_len = current_len;
            result_intervals.clear();
            result_intervals.push_back({left + 1, right + 1});
        } else if (current_len == max_len) {
            result_intervals.push_back({left + 1, right + 1});
        }
    }

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

    return 0;
}

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

class Pair {
    int first, second;
    Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

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> windowCounts = new HashMap<>();
        List<Pair> resultIntervals = new ArrayList<>();
        int maxLen = 0;
        int left = 0;

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

            while (windowCounts.get(a[right]) > 1) {
                windowCounts.put(a[left], windowCounts.get(a[left]) - 1);
                left++;
            }

            int currentLen = right - left + 1;
            if (currentLen > maxLen) {
                maxLen = currentLen;
                resultIntervals.clear();
                resultIntervals.add(new Pair(left + 1, right + 1));
            } else if (currentLen == maxLen) {
                resultIntervals.add(new Pair(left + 1, right + 1));
            }
        }

        System.out.println(resultIntervals.size());
        for (Pair p : resultIntervals) {
            System.out.println(p.first + " " + p.second);
        }
    }
}

from collections import defaultdict

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

window_counts = defaultdict(int)
result_intervals = []
max_len = 0
left = 0

for right in range(n):
    window_counts[a[right]] += 1

    while window_counts[a[right]] > 1:
        window_counts[a[left]] -= 1
        left += 1

    current_len = right - left + 1
    if current_len > max_len:
        max_len = current_len
        result_intervals = []
        result_intervals.append((left + 1, right + 1))
    elif current_len == max_len:
        result_intervals.append((left + 1, right + 1))

print(len(result_intervals))
for start, end in result_intervals:
    print(start, end)

算法及复杂度

  • 算法：双指针（滑动窗口）。
  • 时间复杂度：，虽然存在嵌套的 循环，但 和 指针都只从左到右遍历数组一次，因此总的操作次数是线性的。
  • 空间复杂度：，在最坏情况下（所有元素都不同），哈希表需要存储所有 个元素。