T3无重复字符的最长字串——Java实现

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

• 滑动窗口法，定义两个指针a,b，a指针指向窗口左边界，b指针指向窗口右边界，两者的移动方向均向右。（若a指针移动，则窗口长度缩小，若b指针移动，则窗口长度增大）

• 定义Set数据结构记录窗口元素，便于判断窗口中是否已经存在重复字符

• 当b指针指向的字符已在窗口中存在，先记录此时窗口的长度，随即a指针向右移动，直到定位到窗口中重复元素的后一个元素，将b指针指向的字符保存到Set中，b指针继续右移，重复上述过程。

public int lengthOfLongestSubstring(String s) {
        //使用滑动窗口
        int maxLen = 0;
        Set set = new HashSet<>();
        int rk = 0;
        int i;
        for(i=0;i 
官方代码
 
public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set occ = new HashSet();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

 
官方解答是将rk设为从-1开始，其实它只是一个标志，说明rk还未开始向后移动，代码中实际参与 *** 作的是rk+1
 
 
改进解法 
官方给的解答有一个缺陷就是有很多无效的循环，当遇到重复字符时，还需要一个一个的删除元素，i指针还要一个一个向后移动，直到找到窗口中重复字符的后一个字符，while循环才真正有效
使用HashMap，保存窗口中字符对应的索引值，当遇到重复字符时，直接跳过不必要的for循环，定位到窗口中重复字符的后一个字符
使用的是HashMap，所以遇到重复字符时，省去了删除 *** 作，直接更新重复字符的下标
虽然和上面解法的时间复杂度没差多少，但我可不想做没必要做的事情
 
public int lengthOfLongestSubstring(String s) {
        //使用滑动窗口
        Map map = new HashMap<>();
        int maxLen = 0;
        int rk;
        int i=0;
        for(rk=0;rk 
解法二 
思路 
暴力解法
大家以后第一想法是暴力解法的时候还是放弃吧，对思维没什么用…
 
 
解题收获 
官方解法设置的是左指针不停循环直到字符串的最右边，而改进解法是设置右指针不停循环知道字符串的最右边，如此，就少了判断右指针是否越界的过程
抽象来讲，我知道滑动窗口需要设置两个指针，但是不知道两个指针移动的含义，以及什么时候移动指针
我觉得我说的还有些不准确，后面如果还有想法的话，我会继续更新，不断完善这篇博客，也希望能和大家一起交流
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5677039.html