引言

在当今数字化时代，算法与SQL已成为测试工程师的必备技能。它们不仅是面试的敲门砖，更是解决实际问题的利器。本文将通过两道经典题目——无重复字符的最长子串和分数排名，探讨如何将算法与SQL应用于日志分析、性能监控等测试场景。

算法篇：无重复字符的最长子串

题目描述：给定一个字符串s，找出其中不含有重复字符的最长子串的长度。

测试场景映射：

1. 日志分析：检测日志中连续无重复错误码的最大序列（如错误码连续不重复的时段分析）。
2. 接口测试：验证请求参数的唯一性（如Session ID或Token的连续性检查）。

解题思路：

滑动窗口是一种常用的解决字符串问题的算法。我们可以用哈希集合记录窗口内字符，并动态调整窗口边界。

时间复杂度：O(n)，适合处理长文本或日志流。

代码实现：

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

测试用例设计：

1. 常规测试：assert length_of_longest_substring("abcabcbb") == 3
2. 全重复字符：assert length_of_longest_substring("bbbbb") == 1
3. 空字符串：assert length_of_longest_substring("") == 0
4. 中间有重复：assert length_of_longest_substring("abba") == 2

SQL篇：分数排名

题目描述：为Scores表中的分数生成排名。若两个分数相同，则排名相同，且下一个排名不跳过（即“密集排名”）。

测试场景映射：

1. 性能测试：统计接口响应时间的TOP 10排名。
2. 测试报告：分析测试用例执行失败率的排名。

解题思路：

使用窗口函数DENSE_RANK()可以实现密集排名，按分数降序排列，相同分数共享排名。

SQL实现：

SELECT Score, DENSE_RANK() OVER (ORDER BY Score DESC) AS 'Rank' FROM Scores;

测试用例设计：

1. 创建测试数据：

CREATE TABLE Scores (
    Id INT PRIMARY KEY,
    Score DECIMAL(3, 2)
);

INSERT INTO Scores (Id, Score) VALUES
(1, 3.50),
(2, 3.65),
(3, 4.00),
(4, 3.85),
(5, 4.00),
(6, 3.65);

2. 执行查询并验证结果：

SELECT * FROM Scores ORDER BY Score DESC;

实战应用场景

1. 日志分析问题：如何检测日志中连续无重复错误码的最大序列？解决方案：将日志按时间排序，提取错误码序列。使用滑动窗口算法计算最长无重复子串长度。输出结果并生成告警（如连续无重复错误码超过阈值）。

2. 性能测试排名问题：如何统计接口响应时间的TOP 10排名？解决方案：从性能测试结果表中提取响应时间数据。使用DENSE_RANK()函数生成排名。输出TOP 10结果并生成可视化报告。

总结

通过这两道题目，我们不仅掌握了滑动窗口和窗口函数的核心思想，还将其应用于测试工程师的实际工作场景。这种算法 + SQL + 测试场景的结合，能极大提升我们的技术能力和面试竞争力。

延伸思考

1. 算法题：如何优化滑动窗口的空间复杂度（如用字典代替集合）？
2. SQL题：如果要求相同分数排名相同但下一个排名跳过（如1,1,3），如何修改SQL？

答案参考：

1. 优化滑动窗口的空间复杂度：

def length_of_longest_substring(s: str) -> int:
    char_map = {}
    left = 0
    max_len = 0

    for right in range(len(s)):
        if s[right] in char_map:
            left = max(left, char_map[s[right]] + 1)
        char_map[s[right]] = right
        max_len = max(max_len, right - left + 1)

    return max_len

2. 修改SQL以实现密集排名：

SELECT Score, RANK() OVER (ORDER BY Score DESC) AS 'Rank' FROM Scores;