企业网站建设策划书 前言,html代码颜色表,网络营销事件,国外有哪些网站是做弱电的文章目录 题目示例示例1示例2示例3 解题解法1解法2 leetcode 题目
给定一个字符串 s #xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例
示例1
输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”#xff0c;所以其长度为 3。
示例… 文章目录 题目示例示例1示例2示例3 解题解法1解法2 leetcode 题目
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例
示例1
输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。
示例2
输入: s “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。
示例3
输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。
解题
解法1
粗暴破解找一个最长子串那么我们用两个循环穷举所有子串然后再用一个函数判断该子串中有没有重复的字符。 import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;/*** author zxn* ClassName LongestSubstring* Description* createTime 2023年05月24日 20:33:00*/
public class LongestSubstring {public static void main(String[] args) {String s abcabcbb;int i lengthOfLongestSubstring1(s);System.out.println(ii);}private static int lengthOfLongestSubstring1(String s) {int n s.length();int len0;for (int i 0; i n; i) {for (int j i1; j n; j) {if (unique(s,i,j)){len Math.max(len,j-i1);}}}return len;}public static boolean unique(String s, int start, int end) {SetCharacter set new HashSet();for (int i start; i end; i) {if (set.contains(s.charAt(i))){return false;}set.add(s.charAt(i));}return true;}
解法2
上边的算法中我们假设当 i 取 0 的时候
j 取 1判断字符串 str[0,1) 中有没有重复的字符。
j 取 2判断字符串 str[0,2) 中有没有重复的字符。
j 取 3判断字符串 str[0,3) 中有没有重复的字符。
j 取 4判断字符串 str[0,4) 中有没有重复的字符。
做了很多重复的工作因为如果 str[0,3) 中没有重复的字符我们不需要再判断整个字符串 str[0,4) 中有没有重复的字符而只需要判断 str[3] 在不在 str[0,3) 中不在的话就表明 str[0,4) 中没有重复的字符。
如果在的话那么 str[0,5) str[0,6) str[0,7) 一定有重复的字符所以此时后边的 j 也不需要继续增加了。i 进入下次的循环就可以了。
此外我们的 j 也不需要取 j 1而只需要从当前的 j 开始就可以了。
判断一个字符在不在字符串中我们需要可以遍历整个字符串遍历需要的时间复杂度就是 On加上最外层的 i 的循环总体复杂度就是 On²。我们可以继续优化判断字符在不在一个字符串我们可以将已有的字符串存到 Hash 里这样的时间复杂度是 O1总的时间复杂度就变成了 On。
当 j 指向的 字符 存在于前边的子串中此时 i 向前移到 b ,此时子串中仍然含有字符还得继续移动所以这里其实可以优化。我们可以一步到位直接移动到子串的位置的下一位 import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;/*** author zxn* ClassName LongestSubstring* Description* createTime 2023年05月24日 20:33:00*/
public class LongestSubstring {public static void main(String[] args) {String s abcabcbb;int i lengthOfLongestSubstring2(s);System.out.println(ii);}private static int lengthOfLongestSubstring2(String s) {int n s.length();int len 0;MapCharacter, Integer map new HashMap();for (int i 0, j 0; j n; j) {if (map.containsKey(s.charAt(j))) {i Math.max(i, map.get(s.charAt(j)));}map.put(s.charAt(j), j 1);len Math.max(len, j - i 1);}return len;}
}
leetcode
leetcode地址
