利用HashSet解决无重复字符的最长子串问题

ゝ一纸荒年。 2022-12-03 08:59 101阅读 0赞

利用HashSet解决无重复字符的最长字串问题

> HashSet是基于HashMap来实现的，是一个不允许有重复元素的集合，但是HashSet允许有空值。另外HashSet是无序的，即不会记录插入的顺序。在线程安全方面，它也不是线程安全的，如果多个线程尝试同时修改HashSet，则最终的结果是不正确的。在多线程访问时，必须显式同步对HashSet的并发访问。

HashSet位于java.util包中，使用前需要引入它：

import java.util.HashSet;//引入HashSet类

下面我们利用java中的HashSet解决无重复字符的最长字串问题：

public int lengthOfLongestSubstring(String s){
        //哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        //rk:右指针，初始值为-1，相当于我们在字符串的 左边界的左侧，还没有开始移动
        //ans:记录字串长度
        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;
    }

例如：

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