LeetCode刷题--点滴记录022

偏执的太偏执、 2023-09-28 16:06 28阅读 0赞

## 22. 剑指 Offer 48. 最长不含重复字符的子字符串 ##

**要求**

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

**思路**

动态规划：

*  状态定义： 设动态规划列表 dp ，dp\[j\] 代表以字符 s\[j\] 为结尾的 “最长不重复子字符串” 的长度
 *  转移方程： 固定右边界 j，设字符 s\[j\] 左边距离最近的相同字符为 s\[i\]，即 s\[i\]=s\[j\]  
    当 dp\[j - 1\] < j - i ，说明字符 s\[i\] 在子字符串 dp\[j-1\] 区间之外 ，则 dp\[j\] = dp\[j - 1\] + 1  
    当 dp\[j−1\] ≥ j−i ，说明字符 s\[i\] 在子字符串 dp\[j-1\] 区间之中 ，则 dp\[j\] 的左边界由 s\[i\] 决定，即 dp\[j\] = j - i
 *  返回值： max(dp) ，即全局的 “最长不重复子字符串” 的长度

**解题**

#include <iostream>
    using namespace std;
    #include <vector>
    #include<algorithm>
    
    class Solution {
        
    public:
        int lengthOfLongestSubstring(string s) {
        
            int len = s.size();
            if (s.empty()) 
                return 0;
            vector<int> dp(len + 1, 0);
            for (int j = 1; j < len; j++)
            {
        
                int i = j - 1;
                while (i >= 0 && s[i] != s[j]) 
                    i--;                // 线性查找i
                dp[j] = dp[j - 1] < j - i ? dp[j - 1] + 1 : j - i;  // dp[j - 1] -> dp[j]
            }
            return *max_element(dp.begin(), dp.end());    // 最大值，解引用取值 max(dp[j - 1], dp[j])
        }
    };
    
    
    void test01()
    {
        
        Solution solution;
        string s = "abcabcbb";
        cout << solution.lengthOfLongestSubstring(s) << endl;
    }
    
    int main()
    {
        
        test01();
    
        system("pause");
        return 0;
    }

![在这里插入图片描述][5706ad3c2df349cfbd36c34edac44477.png_pic_center]

**希望本文对大家有帮助，上文若有不妥之处，欢迎指正**

**分享决定高度，学习拉开差距**

[5706ad3c2df349cfbd36c34edac44477.png_pic_center]: https://img-blog.csdnimg.cn/5706ad3c2df349cfbd36c34edac44477.png#pic_center