这道题是LeetCode里的第3道题。
题目描述:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。示例 2:
输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。示例 3:
输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke"是一个子序列,不是子串。
这题可以使用双指针解题,但是不推荐,最好理解的方法就是我这种建立哈希表。但是呢,哈希表可以和双指针一起使用,节约一半的时间。哈希表的用途在于记录该字符是否出现过。
解题代码:
class Solution { public int lengthOfLongestSubstring(String s) { if(s.equals(""))return 0; int maxLength = 0,len = 0; int[] hashMap = new int[128]; int i=0,j=1; hashMap[s.charAt(i)] = 1; len++; while(i < s.length() && j < s.length()) { while(j < s.length()) { if(hashMap[s.charAt(j)] == 1) { hashMap[s.charAt(i)] = 0; i++; len = j - i + 1; if(len > maxLength)maxLength = len; hashMap[s.charAt(i)] = 1; if(j<=i)j = i+1; break; } hashMap[s.charAt(j)] = 1; //len++; j++; } } len = j - i; if(len > maxLength)maxLength = len; return maxLength; }}
提交结果:
个人总结:
双指针:
class Solution { public int lengthOfLongestSubstring(String s) { if(s == null || s.length() == 0) return 0; int start = 0, max = 1; char[] str = s.toCharArray(); for(int j = 1; j < s.length(); j++) { for(int i = start; i < j; i++){ if(str[i] == str[j]) { start = i + 1; break; } } max = Math.max(j - start + 1, max); } return max; }}
双指针的基本思想就是确定开始遍历的字符位置。