leetcode3无重复字符的最长字串（重点讲滑动窗口）

本文主要讲解无重复字符的最长字串的要点与细节，根据步骤一步步走更方便理解

c++与java代码如下，末尾

具体要点：

1. 区分一下子串和子序列

        子串：要求元素在母串中是连续地出现

        子序列：不要求连续

---

2. 题目中有两个核心要点：无重复，最长

        无重复：我们可以想到哈希表来解决（哈希表用来判断一个元素是否出现过）

        最长：我们可以利用滑动窗口的思路来解决（滑动窗口通常用来解决某种连续性子序列条件）

---

3. 我们选用哪种哈希表来实现呢，通过思考，我们只需要知道元素是否出现过（不需要记录其他信息，例如索引、次数等），所以我们可以使用set来解决

---

4. 解决了无重复的问题，我们思考一下滑动窗口具体应该怎么实现？

        滑动窗口通常都是两个指针，一个right一个left

        开始时我们先移动right，判断条件是：right始终不越界 + right的值始终没有出现过

即             while (right < s.size() && hashset.find(s[right]) == hashset.end())

        移动right并加入set中

即            hashset.insert(s[right]);
                right++;

        直到right不能再移动后，我们记录最大长度，并移动一次left，同时把left的值从set中删除 

即        //更新最大长度

            result = max(result, right - left);

            //删除left并移动left

            hashset.erase(s[left]);

            left++;

        至此，实现一轮滑动（每一轮都只移动一次left） 

---

c++代码

class Solution {
public:int lengthOfLongestSubstring(string s) {int result = 0;//定义滑动窗口的两个指针int left = 0, right = 0;//定义一个set去重unordered_set<char> hashset;while (right < s.size()) {//不断移动rightwhile (right < s.size() && hashset.find(s[right]) == hashset.end()) {hashset.insert(s[right]);right++;}//更新最大长度result = max(result, right - left);//移动lefthashset.erase(s[left]);left++;}return result;}
};

java代码

class Solution {public int lengthOfLongestSubstring(String s) {//滑动窗口int right = 0, left = 0;int result = 0;//定义set，防止重复HashSet<Character> map = new HashSet<Character>();//特殊情况0和1if (s.length() == 0 || s.length() == 1) {return s.length();}while (s.length() > right) {//right位置如果没有出现过，就addwhile (s.length() > right && !map.contains(s.charAt(right))) {map.add(s.charAt(right));right++;}result = Math.max(result, right - left);//right移动到不能移动，就开始移动leftmap.remove(s.charAt(left));left++;}return result;}
}