欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Leetcode Two Sum (java)Longest Substring Without Repeating Characters

程序员文章站 2022-03-16 22:28:05
解法一: 这种解法使用的是Brute Force算法,即是暴力搜索匹配,时间复杂度较高 解法二: 这种解法的思想是计算两个相同的字符之间的长度,好比作一个窗口在字符串上右边框向右拉伸,若右边框碰到窗口内已存在的字符,那么左边框向右拉伸到到窗口已存在字符的右边,时间复杂度较低 github地址:htt ......

解法一:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        if (s.length() <= 1) {
            max = s.length();
            return max;
        }
        for (int i = 0; i < s.length(); i++) {
            //新建一个StringBuilder存储临时字符串
            StringBuilder str = new StringBuilder();
            str.append(String.valueOf(s.charAt(i)));
            //判断每个字符串多长
            for (int j = i + 1; j < s.length(); j++) {
                //当出现相同字符串则停止匹配跳出
                if (str.indexOf(String.valueOf(s.charAt(j))) == -1) {
                    str.append(String.valueOf(s.charAt(j)));
                }
                else{
                    break;
                }
            }
            //记录最大长度
            if (str.length() > max) {
                max = str.length();
            }
        }
        return max;
    }
}

 这种解法使用的是Brute Force算法,即是暴力搜索匹配,时间复杂度较高

 

解法二:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        //存储每个字符出现的位置
        Hashtable<Character, Integer> map = new Hashtable<Character, Integer>();
        //遍历字符串
        for (int i = 0, j = 0; i < s.length(); i++) {
            //当出现相同字符时改变窗口左边框位置并记录窗口长度
            if (map.containsKey(s.charAt(i))) {
                j = Math.max(map.get(s.charAt(i)) + 1 , j);
            }
            max = Math.max(max, i - j + 1);
            map.put(s.charAt(i), i);
        }
        return max;
    }
}

 这种解法的思想是计算两个相同的字符之间的长度,好比作一个窗口在字符串上右边框向右拉伸,若右边框碰到窗口内已存在的字符,那么左边框向右拉伸到到窗口已存在字符的右边,时间复杂度较低


github地址:https://github.com/CyanChan/leetcode