数据结构学习 Jz48最长不含重复字符的子字符串

关键词：哈希表 动态规划 滑动窗口

用时：40min 哈希表 动态规划

题解：我觉得这个写的很好。

题目：

方法一：

哈希表 滑动窗口

思路：

我一开始没想到用一个左指针做滑动窗口。

哈希表：存之前出现过的字符最后出现的位置。

左指针l：记录上一个字符所组成的最长不含重复字符的子字符串的左边界。

如果出现了和前面一样的字符，则更新左指针。

注意，如果pre->second+1<l，说明这个重复的数不在我们现在统计的这个区间里面，所以可以直接忽略，所以l=l。

l=std::max(l,pre->second+1);

复杂度计算：

时间复杂度O(n)

空间复杂度O(1)

字符的 ASCII 码范围为 0?~ 127 ，哈希表最多使用 O(128)=O(1) 大小的额外空间。

代码：

class Solution {
public:
    int dismantlingAction(std::string arr) {
        std::unordered_map<char, int> hash;
        int max = 0;
        int res=0;
        if (arr.empty())return max;
        int l=0;
        for(int i=0;i<arr.size();++i)
        {
            auto pre = hash.find(arr[i]);
            if(pre!=hash.end())
            {
                l=std::max(l,pre->second+1);
            }
            hash[arr[i]]=i;
            max=std::max(max,i-l+1);
        }
        return max;
    }
}; 

方法二：

哈希表 动态规划

我一开始想到的是这个方法。

思路：

哈希表：存之前出现过的字符最后出现的位置。

dp状态：

dp[i]以第i个字符为最后一个字符的最长不重复字符串。

转移函数：

1、如果arr[i]没有出现过：

dp[i]=dp[i-1]+1 不重复的字符串又长了

2、如果arr[i]出现过：

这里又分两种情况：

i-pre->second<dp[i-1]+1：

说明上一个重复的字符串，被算进了dp[i-1]区间里面，所以dp[i]=i-pre->second

i-pre->second>=dp[i-1]+1：

说明上一个重复的字符串，没被算进dp[i-1]区间里面，所以dp[i]=dp[i-1]+1

复杂度计算：

时间复杂度O(n)

空间复杂度O(1)

字符的 ASCII 码范围为 0?~ 127 ，哈希表最多使用 O(128)=O(1) 大小的额外空间。

代码：

class Solution {
public:
    int dismantlingAction(std::string arr) {
        std::unordered_map<char, int> hash;
        int max = 0;
        int dp = 0;
        if (arr.empty())return max;
        for (int i = 0; i < arr.size(); ++i)
        {
            auto pre = hash.find(arr[i]);
            if (pre == hash.end())
            {
                dp++;
                max = std::max(max, dp);
            }
            else
            {
                dp = std::min(i - pre->second, ++dp);
                max = std::max(max, dp);

            }
            hash[arr[i]] = i;
        }
        return max;
    }
};