3. 无重复字符的最长子串

曾经终败给现在 2021-09-21 14:28 354阅读 0赞

package com.cheng.leetcode;
 
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;
 import java.util.Set;
 
 /** * @author c * @create 2020-12-23 19:41 * * 3. 无重复字符的最长子串 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 * * * * 示例 1: * * 输入: s = "abcabcbb" * 输出: 3 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 * 示例 2: * * 输入: s = "bbbbb" * 输出: 1 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 * 示例 3: * * 输入: s = "pwwkew" * 输出: 3 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 * 示例 4: * * 输入: s = "" * 输出: 0 * * * 提示： * * 0 <= s.length <= 5 * 104 * s 由英文字母、数字、符号和空格组成 * 通过次数768,233提交次数2,131,745 */
 public class Demo0003 { 
 /* 本人的算法，使用暴力求解 */
 public int lengthOfLongestSubstring1(String s) { 
 //判断如果等于0 则返回结果为0
 if (s.length() == 0) { 
 return 0;
 }
 //将对应字符串转化为字节数组
 char[] chars = s.toCharArray();
 //目标字符串
 StringBuilder str = new StringBuilder();
 //定义中间量
 int res = 0;
 //定义最大值
 int max = 0;
 //第一个for 以不同的位置作为起点开始便利
 for (int i = 0; i < chars.length; i++) { 
 //以i为起点便利 得到以此节点为头的最长子串
 for (int j = i; j < chars.length; j++) { 
 //判断子串中是否包含此字符--》推荐使用 set集合来表示
 if (!str.toString().contains(new StringBuilder(String.valueOf(chars[j])))) { 
 //如果不包含当前字符，则中间值加一
 res++;
 //将此字符加入到子串中
 str.append(chars[j]);
 //给最大值赋值
 if (max <= res) { 
 max = res;
 }
 } else { 
 //如果重复则清空子串
 str = new StringBuilder();
 //将中间值清零
 res = 0;
 //终止循环
 break;
 }
 }
 }
 return max;
 }
 
 /* 网上找的思路：滑动窗口 什么是滑动窗口？ 其实就是一个队列，比如例题中的abcabcbb，进入这个队列（窗口）为abc 满足题目要求，当再进入a，队列变成了abca，这时候不满足要求。所以，我们要移动这个队列！ 如何移动？ 我们只要把队列的左边的元素移出就行了，直到满足题目要求！一直维持这样的队列，找出队列出现最长的长度时候，求出解！ 当然滑动窗口的尺寸可以是固定也可以是动态的 时间复杂度：O（2n）=O（n），在最糟糕的情况下，每个字符将被i和j访问两次。 空间复杂度：O（min（m，n）），与之前的方法相同。滑动窗口法需要O（k）的空间，其中k表示Set的大小。而Set的大小取决于字符串n的大小以及字符集/字母m的大小。 */
 public int lengthOfLongestSubstring2(String s) { 
 //判断如果等于0 则返回结果为0
 if (s.length() == 0) { 
 return 0;
 }
 //将对应字符串转化为字节数组
 char[] chars = s.toCharArray();
 int n = s.length();
 int left = 0;
 int right = 0;
 //存储字符的集合
 Set<Character> str = new HashSet<>();
 //定义最大值
 int max = 0;
 //从左向右便利
 while (left < n && right < n) { 
 //判断是否包含右边的元素
 if (!str.contains(chars[right])) { 
 //如果不包含将右边的字符加入集合
 str.add(chars[right]);
 //右移
 right++;
 //判断最大值
 max = Math.max(max, right - left);
 } else { 
 //如果包含右边的元素，则移除最左边的元素
 str.remove(chars[left]);
 //左值针加一
 left++;
 }
 }
 return max;
 }
 
 /* 优化滑动窗口 上述的方法最多需要执行2n个步骤。 事实上，它可以被进一步优化为仅需要n个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。 也就是说，如果s[j]在[i，j）范围内有与j重复的字符，我们不需要逐渐增加i。 我们可以直接跳过[i，j门范围内的所有元素，并将i变为j+1。 时间复杂度：O（n），索引j将会迭代n次。 空间复杂度（HashMap）：O（min（m，n）），与之前的方法相同。 空间复杂度（Table）：O（m），m是字符集的大小。 */
 public int lengthOfLongestSubstring3(String s) { 
 int n = s.length();
 Map<Character, Integer> map = new HashMap<>();
 //定义最大值
 int max = 0;
 for (int left = 0, right = 0; right < n; right++) { 
 //直接将左边的指针指向重复位置
 if (map.containsKey(s.charAt(right))) { 
 left = Math.max(left, map.get(s.charAt(right)));
 }
 //设置最大值
 max = Math.max(max, right - left + 1);
 //将右边元素添加到集合
 map.put(s.charAt(right), right + 1);
 }
 return max;
 }
 
 
 public static void main(String[] args) { 
 String s = "tmmzuxt";
 System.out.println(new Demo0003().lengthOfLongestSubstring3(s));
 }
 
 }

暴力求解  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29qZW1tbQ_size_16_color_FFFFFF_t_70_pic_center]

滑动窗口  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29qZW1tbQ_size_16_color_FFFFFF_t_70_pic_center 1]

优化滑动窗口  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29qZW1tbQ_size_16_color_FFFFFF_t_70_pic_center 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29qZW1tbQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20210920/0b8de852de084941b65086da8b015b92.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29qZW1tbQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20210920/844d9fb8408747d3bdf9306b13d49dd6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29qZW1tbQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20210920/eaba11eaca94463c96191ff0835e489d.png