织梦dedecms医院类网站在线预约挂号插件,山西建设网站的公司,北京软件开发培训班,app store免费下载给定一个字符串#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc#xff0c;所以其长度为 3。 示例 2:
输入: bbbbb 输出: 1 解释: 因为无重复字符…给定一个字符串请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc所以其长度为 3。 示例 2:
输入: bbbbb 输出: 1 解释: 因为无重复字符的最长子串是 b所以其长度为 1。 示例 3:
输入: pwwkew 输出: 3 解释: 因为无重复字符的最长子串是 wke所以其长度为 3。 请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。
思路
如果直接使用暴力法时间复杂度将会是o(n^3),不可取也无法通过案例测试
双指针法使用滑动窗口
在暴力法中我们会反复检查一个子字符串是否含有有重复的字符但这是没有必要的。
我们可以设定左右边界i为左边界j为右边界j从0开始向右移动当遇到重复元素时j开始向右移动将与该元素重复的那个元素之间的元素都去掉之后j继续移动。
例如abcbdbb
初始i0j0
j开始向右移动i0j2现在长度为3
j继续移动j3发现有重复元素那么i开始移动
先去掉a发现重复元素还在继续移动去掉第一个b元素现在没有重复元素我们可以继续向下走了
此时i2j3
那么如何去掉重复元素呢
Java中提供了set他可以帮助我们很好的去重
提交的代码
class Solution { public int lengthOfLongestSubstring(String s) { int n s.length(); int i0,j0,sum0,max0; SetCharacter set new HashSet(); while(injn) { if(set.contains(s.charAt(j))false) { set.add(s.charAt(j)); j; sum1; } else { set.remove(s.charAt(i)); i; sum-1; } max java.lang.Math.max(max, sum); } return max; } }
完整的代码
import java.util.HashSet; import java.util.Scanner; import java.util.Set;
public class Solution3 { public static int lengthOfLongestSubstring(String s) { int n s.length(); int i0,j0,sum0,max0; SetCharacter set new HashSet(); while(injn) { if(set.contains(s.charAt(j))false) { set.add(s.charAt(j)); j; sum1; } else { set.remove(s.charAt(i)); i; sum-1; } max java.lang.Math.max(max, sum); } return max; } public static void main(String[] args) { Scanner sc new Scanner(System.in); String s; s sc.nextLine(); System.out.println(lengthOfLongestSubstring(s)); } }
