无重复字符的最长字串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

滑动窗口：维护一个左指针和一个右指针，维护窗口两端的索引，且 right 每次向右走一个索引。建一个无序集合来存储现在窗口中的字符，出现重复就将窗口左索引向右移动，直到 right 加入的新字符无重复为止，随后加入 s[right]。每次完成新元素加入时更新最大窗口长度，得到最大窗口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> window;
        int left = 0, maxLen = 0;
        int str_size = s.size();
        
        for (int right = 0; right < str_size; ++right) {
            while (window.count(s[right])) {
                window.erase(s[left]);
                ++left;
            }
            window.insert(s[right]);
            maxLen = max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

这个方法似乎效率有些低？反复对 unordered 做加入和擦除操作会拖慢运行速度。用一个长度为 128（或 256，覆盖 ASCII）的 int 数组 lastPos，初始值为 -1，记录每个字符最近一次出现的索引。 右指针 right 遍历时：

  • 如果 lastPos[s[right]] >= left，说明当前字符在窗口内重复，直接将 left 跳到 lastPos[s[right]] + 1，无需循环。
  • 更新 lastPos[s[right]] = right，计算当前窗口长度。
    这样完全去掉了哈希集合和内层 while 循环，每个字符只有一次数组读写，常数极小。

被刚会用的哈希坑了啊。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> lastPos(128, -1);
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.size(); ++right) {
            char c = s[right];
            if (lastPos[c] >= left) {
                left = lastPos[c] + 1;
            }
            lastPos[c] = right;
            maxLen = max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

也是滑动窗口，但是是固定宽度的。

用两个长度为 26 的数组 pCount 和 windowCount 记录字符出现次数。初始时统计 p 的频率，以及 s 前 p.size() 个字符的频率。若两数组相等，记录起始索引 0。窗口每次右移一位,加入右边新字符，移除左边旧字符，更新频率后比较。相等则记录左边界索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        int sLen = s.size(), pLen = p.size();
        if (sLen < pLen) return result;

        vector<int> pCount(26, 0), windowCount(26, 0);
        for (int i = 0; i < pLen; ++i) {
            pCount[p[i] - 'a']++;
            windowCount[s[i] - 'a']++;
        }
        if (pCount == windowCount) result.push_back(0);

        for (int i = pLen; i < sLen; ++i) {
            windowCount[s[i] - 'a']++;
            windowCount[s[i - pLen] - 'a']--;
            if (pCount == windowCount) {
                result.push_back(i - pLen + 1);
            }
        }
        return result;
    }
};