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
下一篇: 如何解决系统时间无法修改的问题
推荐阅读
-
Longest Substring Without Repeating Characters
-
LeetCode - 3.Longest Substring Without Repeating Characters(388ms)
-
[LeetCode]3.Longest Substring Without Repeating Characters
-
Leetcode_3. Find the longest substring without repeating characters
-
3-Longest Substring Without Repeating Characters @LeetCode
-
Longest Substring Without Repeating Characters (leetcode 3)
-
【Leetcode 3】Longest Substring Without Repeating Characters
-
Leetcode 3 Longest Substring Without Repeating Characters
-
leetcode【3】Longest Substring Without Repeating Characters
-
LeetCode(3)Longest Substring Without Repeating Characters