https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

方法一 暴力法(官方解析用HashSet 我偏不用)

// 暴力法 算法复杂度O(N^2)
    public int lengthOfLongestSubstring(String s) {
        // 初始化返回值
        int ans = 0;
        // 字符串为空返回0
        if (s == null || s.equals("")) return ans;
        char[] chars = s.toCharArray();
        //每次将i的作为起始位
        for (int i = 0; i < chars.length; i++) {
            int temp = 0;
            System.out.println(i);
            // 初始化Map 每次循环都要重新构造 判断构造的字符串中的字符是否重复
            Map<Character, Integer> map = new HashMap<>();
            for (int j = i; j < chars.length; j++) {
                // 判断构造的字符串中的字符是否重复
                if (!map.containsKey(chars[j])){
                    temp += 1;
                } else {
                    break;
                }
                map.put(chars[j], j);
            }
            // 取最大值
            ans = Math.max(ans, temp);
        }
        return ans;
    }

方法二 滑动窗口

// 滑动窗口
    public int lengofLonger(String s){
        // 初始化返回值
        int ans = 0;
        // 字符串为空返回0
        if (s == null || s.equals("")) return ans;
        // 当前窗口的最左端
        int left = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                // 构造的字符串包含字符就重新搞最左边
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            ans = Math.max(ans, i-left+1);
        }
        return ans;
    }
最后修改:2021 年 02 月 27 日
如果觉得我的文章对你有用,请随意赞赏