阅读 232

用滑动窗口来解决最长无重复子串问题

题目描述

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

示例1:

输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例2:

输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例3:

输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

解法1:滑动窗口

滑动窗口是解决字符串和数组类问题的一个重要工具。就本地而言,我们使用如下解题思路:

  1. 假设输入字符串为:pwwkew
  2. 初始化map, key为字符,value为该字符在输入字符串中的位置。
  3. 初始化i=0,j=0。
  4. 查看j所对应的元素newJValue是否否在与map中:
    1. 如果它在map中,则从map中删除i所指向的元素,并将i向右滑动,继续执行4。
    2. 如果它不在map中,则将其插入到map,并将j向右滑动,继续执行4。并起来当前最大值m。
class Solution {
public:
    int lengthOfLongestSubstring(string str) {
        int i = 0;
        int j = 0;
        int m = 0;
        int size = (int)str.size();
        
        map<char, int> tmap;
        while (i<size && j<size) {
            if (tmap.find(str[j]) == tmap.end()) {
                tmap.insert(pair<char, int>(str[j], j));
                j++;
                m = max(m, j-i);
            } else {
                tmap.erase(tmap.find(str[i]));
                i++;
            }
        }
        return m;
    }
};
复制代码

优化代码

这里的优化思路是:当i需要向右滑动的时候不需要一次一次的滑动,而是直接跳到新的重复元素。

举例来说,对于测试用例:pwwkew来讲。

当j=2,i=0是,map中已经有了pw了,对于j=2的w在map中已经存在w,所以此时需要将i右滑两次,只是我们可以直接将i跳到2,而不用一步一步的滑动。具体代码如下:

int lengthOfLongestSubstring(string str) {
        int i = 0;
        int j = 0;
        int m = 0;
        int size = (int)str.size();
        
        map<char, int> tmap;
        while (j<size) {
            if (tmap.find(str[j]) != tmap.end()) {
                i = max(tmap.find(str[j])->second, i);
            }
            m = max(m, j-i+1);
            tmap[str[j]] = j+1;
            j++;
        }
        return m;
    }
复制代码

交流学习

交流学习

关注下面的标签,发现更多相似文章
评论