力扣——3. 无重复字符的最长子串

题目：

 思路：

字符串匹配问题

1.滑动窗口实现
定义两个指针、一个字符集合，指针初始位置都指向字符串最左侧，此时右指针右移，判断右指针指向的元素是否包含在字符集合中，如果包含就将该字符从字符集合中移除，并将左指针右移一位，如果不包含就将该字符添加到字符集合中，重复以上步骤，并记录这个过程中窗口（字符集合字符个数/左右指针之差+1）的最大值，即所求的最长子串长度。
细节

• HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。

参考链接：(97条消息) Set set=new HashSet()；的意义是什么呢_ll123c的博客-CSDN博客

• charAt() 方法用于返回指定索引处的字符。索引范围为从 0 到 length() - 1。

代码1：

    public int lengthOfLongestSubstring(String s) {
        int sLen = s.length(),matchLen = 0;
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0, j = 0; j < sLen; j++) {
            //如果存在重复字符，将窗口滑到重复字符的地方
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)),i);
            }
            matchLen = Math.max(matchLen,j-i+1);
            map.put(s.charAt(j),j+1);
        }
        return matchLen;
    }

代码2:

class Solution {
    public int lengthOfLongestSubstring(String s) {
    	if (s.length() <= 1) {
            return s.length();
        }
        //定义窗口的最大值
        int longestLength = 0;
        //定义左右指针
        int left = 0;
        int right = 0;
        //定义窗口字符集合
        Set<Character> set = new HashSet<>();
        //当左右指针到达边界值时结束循环
        while (left < s.length() && right < s.length()) {
            //判断窗口集合是否包含指针处字符
            if (set.contains(s.charAt(right))) {
                //包含就移除集合中指针处字符，并右移左指针
                set.remove(s.charAt(left));
                left++;
            } else {
                //不包含就将指针处字符添加到集合中，并右移右指针
                set.add(s.charAt(right));
                right++;
            }
            //更新窗口最大值
            if (set.size() > longestLength) {
                longestLength = set.size();
            }
        }
        return longestLength;
    }
 }

参考链接：

(97条消息) LeetCode3. 无重复字符串的最长子串Java实现及思路详解_彼岸啊的博客-CSDN博客

(97条消息) java无重复字符的最长子串_下雨了_简的博客-CSDN博客