题解 | #连续子序列#

题目链接

连续子序列

题目描述

在网络安全日志分析系统中，给定一个由 ASCII 字母和数字组成的事件编码序列 $s$ 。请找到其中最长的一段连续子序列，使得这段子序列中每个字符都不相同，并输出该子序列的长度。字符串长度 $n$ 最大可达 $10^7$ 。

解题思路

这是一个经典的“无重复字符的最长子串”问题，可以使用**滑动窗口（双指针）**算法在 $\mathcal{O}(n)$ 时间内解决。

定义窗口：使用两个指针 $left$ 和 $right$ 表示当前的窗口范围 $[left, right]$ 。该窗口内的所有字符都是唯一的。
维护位置信息：使用一个数组（或哈希表） $pos$ 来记录每个字符最后一次出现的位置索引。由于输入仅包含 ASCII 字母和数字，我们可以使用一个长度为 $128$ 的数组来覆盖所有可能的 ASCII 字符。
滑动窗口逻辑：
- 遍历字符串，移动右指针 $right$ 。
- 如果当前字符 $s[right]$ 之前已经出现过，且其最后出现的位置在当前窗口 $left$ 之后（或等于 $left$ ），说明窗口内出现了重复。
- 此时，我们需要将左指针 $left$ 移动到该重复字符上一次出现位置的下一个位置，即 $left = pos[s[right]] + 1$ 。
- 每次移动 $right$ 后，更新该字符的最后出现位置 $pos[s[right]] = right$ 。
- 同时计算当前窗口的长度 $right - left + 1$ ，并维护全局最大长度 $ans$ 。
性能优化：考虑到字符串长度 $n = 10^7$ 较大，使用固定长度的数组代替映射表（如 map）可以显著提升处理速度并降低内存开销。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 使用滑动窗口算法，时间复杂度为 O(n)
 * 由于字符串长度达到 10^7，使用数组存储字符位置以保证效率
 */

int main() {
    string s;
    // 读取输入字符串
    cin >> s;

    int n = s.length();
    // 使用数组记录字符最后一次出现的位置，初始化为 -1
    vector<int> last_pos(128, -1);
    
    int left = 0;
    int ans = 0;
    
    for (int right = 0; right < n; ++right) {
        char c = s[right];
        // 如果字符在当前窗口中出现过，移动左边界
        if (last_pos[c] >= left) {
            left = last_pos[c] + 1;
        }
        // 更新字符最后出现的位置
        last_pos[c] = right;
        // 更新最大长度
        int current_len = right - left + 1;
        if (current_len > ans) {
            ans = current_len;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取输入字符串
        String s = sc.next();
        int n = s.length();
        
        // 使用数组记录字符最后一次出现的位置，初始化为 -1
        int[] lastPos = new int[128];
        for (int i = 0; i < 128; i++) {
            lastPos[i] = -1;
        }
        
        int left = 0;
        int ans = 0;
        
        for (int right = 0; right < n; right++) {
            char c = s.charAt(right);
            // 如果该字符上一次出现的位置在当前窗口内，更新左指针
            if (lastPos[c] >= left) {
                left = lastPos[c] + 1;
            }
            // 更新字符出现位置
            lastPos[c] = right;
            // 计算当前无重复子串长度
            int currentLen = right - left + 1;
            if (currentLen > ans) {
                ans = currentLen;
            }
        }
        
        System.out.println(ans);
    }
}

def solve():
    # 读取输入字符串
    s = input()
    n = len(s)
    
    # last_pos 字典记录字符最后一次出现的位置
    last_pos = {}
    left = 0
    ans = 0
    
    for right in range(n):
        char = s[right]
        # 如果字符已经在字典中，且位置在 left 之后，说明重复，需要收缩窗口
        if char in last_pos and last_pos[char] >= left:
            left = last_pos[char] + 1
        
        # 更新字符位置
        last_pos[char] = right
        # 计算当前长度并更新最大值
        current_len = right - left + 1
        if current_len > ans:
            ans = current_len
            
    print(ans)

solve()

算法及复杂度

算法：滑动窗口（双指针）。
时间复杂度： $\mathcal{O}(n)$ 。其中 $n$ 为字符串长度。我们只需要对字符串进行一次线性扫描。
空间复杂度： $\mathcal{O}(|\Sigma|)$ 。其中 $|\Sigma|$ 是字符集的大小。由于本题限定为 ASCII 字母和数字，数组或字典的大小固定为常数级别（如 $128$ ），在计算总复杂度时可视作 $\mathcal{O}(1)$ 的额外空间，但考虑存储字符串本身，总空间复杂度为 $\mathcal{O}(n)$ 。