【leetcode算法-无重复字符的最长子串】
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。1、暴力破解
package leetcode;
import java.util.HashSet;
public class Demo2 {
public static int LengthOfLongestSubstring(String str)
{
int resLength = 0;
int strLength = str.length();
HashSet<String> hashSet = new HashSet<String>();
for (int i = 0; i < strLength; i++)
{
for (int j = i + 1; j < strLength; j++)
{
//这里能确定str的所有子串
String strChildren = str.substring(j, j+1);
if (hashSet.contains(strChildren))
{
break;
}
else
{
hashSet.add(strChildren);
}
}
}
return resLength;
}
public static void main(String[] args) {
System.out.println(Demo2.LengthOfLongestSubstring("ababedf"));
}
}2、大佬解法
滑动窗口，通过使用 HashSet 作为滑动窗口，我们可以用 O(1) 的时间来完成对字符是否在当前的子字符串中的检查。滑动窗口是数组/字符串问题中常用的 抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j)（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [i, j)向右滑动 1 个元素，则它将变为 [i+1, j+1)（左闭，右开）。
回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i, j)（最初 j = i）中。 然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i开头。如果我们对所有的 i 这样做，就可以得到答案。
2.1、代码实现
public static int LengthOfLongestSubstring3(String str)
{
int resLength = 0;
int strLength = str.length();
int i = 0, j = 0;
HashSet<String> hashSet = new HashSet<String>();
while (i < strLength && j < strLength)
{
String oneStrJ = str.substring(j,j+1);
if (!hashSet.contains(oneStrJ))
{
hashSet.add(oneStrJ);
j++;
resLength = Math.max(resLength,j-i);
}
else
{
String oneStrI = str.substring(i, i+1);
hashSet.remove(oneStrI);
i++;
}
}
return resLength;
}2.2 代码实现：
（1）快指针j所在元素不重复，更新max，将快指针j元素在hash表中的标记为出现，后移j ； （2）快指针j所在元素重复，慢指针后移，此时将慢指针i元素在hash表中的标记清除。此时并不关心是谁重复，重复元素前的元素都要清除掉。
public static int lengthOfLongestSubstring(String s) {
int []hash = new int [500];
int max = 0;
int i = 0, j = 0;
while (i < s.length() && j <s.length() ) {
if(hash[s.charAt(j)] == 0) {
hash[s.charAt(j)] = 1;
j++;
max = (j - i) > max ? (j - i) : max;
} else {
hash[s.charAt(i)] = 0;
i++;
}
}
return max;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读