关于java:Note剑指Offer48

1次阅读

共计 871 个字符，预计需要花费 3 分钟才能阅读完成。

请从字符串中找出一个最长的不蕴含反复字符的子字符串，计算该最长子字符串的长度。

双指针 +HashSet
当不是反复的字符，放进 set 并且 i ++；res 记录最大长度
当遇到 j 指向的字符放不进去，就删掉后面的字符并且 i ++，直到指向的字符能放进去
工夫复杂度 O（2n）

package offer;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/**
 * 请从字符串中找出一个最长的不蕴含反复字符的子字符串，计算该最长子字符串的长度。*/public class offer48 {public static void main(String[] args) {Scanner scc=new Scanner(System.in);
        String s=scc.next();
        System.out.println(new Solution48().lengthOfLongestSubstring(s));
    }
}
class Solution48 {public int lengthOfLongestSubstring(String s) {int n=s.length();
        Set<Character> set =new HashSet<>();
        int res =0,i=0,j=0;
        while(i<n&&j<n) {if(!set.contains(s.charAt(j))) {// 当不是反复的字符，放进 set 并且 i ++；res 记录最大长度
                set.add(s.charAt(j++));
                res=Math.max(res, j-i);
            }
            else {set.remove(s.charAt(i++));// 当遇到 j 指向的字符放不进去，就删掉后面的字符并且 i ++，直到指向的字符能放进去
            }
        }
        return res;
    }
}