精选力扣500题第4题 LeetCode 3. 无重复字符的最长子串【c++详细题解】

た入场券 2021-07-24 19:28 227阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

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

**示例 1:**

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

**示例 2:**

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

**示例 3:**

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

**示例 4:**

输入: s = ""
    输出: 0

**提示：**

*  `0 <= s.length <= 5 * 104`
 *  s 由英文字母、数字、符号和空格组成

### 2、思路 ###

**(双指针扫描)**  O ( n ) O(n) O(n)

定义两个指针  i , j ( i < = j ) i,j(i<=j) i,j(i<=j)，表示当前扫描到的子串是  \[ i , j \] \[i,j\] \[i,j\] (闭区间)。扫描过程中维护一个哈希表`unordered_map <chat,int>hash`，表示  \[ i , j \] \[i,j\] \[i,j\]中每个字符出现的次数。

线性扫描时，每次循环的流程如下：

*  1.指针 j 向后移一位, 同时将哈希表中 s\[j\] 的计数加一:`hash[s[j]]++`;
 *  2.假设 j 移动前的区间  \[ i , j \] \[i,j\] \[i,j\]中没有重复字符，则 j 移动后，只有  s \[ j \] s\[j\] s\[j\]可能出现2次。因此我们不断向后移动 i，直至区间 \[i,j\]中 s\[j\] 的个数等于1为止；

复杂度分析：由于 i,j 均最多增加n次，且哈希表的插入和更新操作的复杂度都是  O ( 1 ) O(1) O(1)，因此，总时间复杂度  O ( n ) O(n) O(n).

### 3、代码 ###

class Solution { 
    public:
        int lengthOfLongestSubstring(string s) { 
            unordered_map<char,int>hash;
            int res =  0;
            for(int j = 0 ,i = 0; j < s.size(); j++)
            { 
                hash[s[j]]++;
                while(hash[s[j]] > 1)
                { 
                    hash[s[i++]]--;       
                }
                res = max(res,j-i+1);
            }
            return res;
        }
    };

**原题链接：**[3. 无重复字符的最长子串][3.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[3.]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/ce6e90b691c642329286963024b8be24.png