极客笔记Java 找到最长的无重复字符子串的长度
子串是字符串中包含连续字符的部分，可以是任意长度从1到完整字符串。给定一个字符串，我们要找到给定字符串中只包含独特字符的最大子串的长度。我们将看到三种方法：找到每个子串、滑动窗口和双指针。
方法1（找到每个子串）
在这种方法中，我们将得到每个子串，然后检查是否存在重复的字符。
示例
public class Solution{
// function to check the unique characters
public static boolean isUnique(String str, int i, int j){
// array to store the non-unique characters
boolean arr[] = new boolean[26];
// traversing over the string
while(i <= j){
if(arr[str.charAt(i)-'a'] == true){
return false; // returning false as answer
}
else{
arr[str.charAt(i)-'a'] = true;
}
i++;
}
return true; // returning true
}
// function to get the required substring
public static int longestSubStr(String str){
int len = str.length();
int ans = 0; // variable to store the answer
// traversing over the string
for(int i=0; i<len; i++){
// function to get every substring starting from here
for(int j = i; j<len; j++){
// calling function to check if the current substring contains the unique characters
if(isUnique(str, i,j)){
ans = Math.max(ans, j-i+1);
}
}
}
return ans; // return the final answer
}
// main function
public static void main(String []args){
String str = "thisisthegivenstring"; // given string
// calling to the function
int ans = longestSubStr(str);
// print the final answer
System.out.println("The length of the longest substring that contains only unique characters is: " + ans );
}
}
输出
The length of the longest substring that contains only unique characters is: 8
时间和空间复杂度
上述代码的时间复杂度是O(N^3)，其中N是给定字符串的长度。
上述代码的空间复杂度是常数或O(1)，因为我们在这里没有使用任何额外的空间。
方法2（滑动窗口）
在这个方法中，我们将通过使用指针创建一个窗口，并在窗口中遍历字符串，直到窗口中没有重复字符为止。
示例
public class Solution{
// function to get the required substring
public static int longestSubStr(String str){
int len = str.length();
int ans = 0; // variable to store the answer
// traversing over the string
for(int i=0; i<len; i++){
// array to store the non-unique characters
boolean arr[] = new boolean[26];
// function to get every substring starting from here
for(int j = i; j<len; j++){
if(arr[str.charAt(j)-'a'] == true){
break;
}
else{
arr[str.charAt(j)-'a'] = true;
ans = Math.max(ans,j-i+1);
}
}
}
return ans; // return the final answer
}
// main function
public static void main(String []args){
String str = "thisisthegivenstring"; // given string
// calling to the function
int ans = longestSubStr(str);
// print the final answer
System.out.println("The length of the longest substring that contains only unique characters is: " + ans );
}
}
输出
The length of the longest substring that contains only unique characters is: 8
时间和空间复杂度
上面代码的时间复杂度是O(N^2)，其中N是给定字符串的长度。
上面代码的空间复杂度是常数或O(1)，因为我们在这里没有使用任何额外的空间。
方法3（双指针）
在这种方法中，我们将使用双指针的概念，将一个指针移动得较慢，另一个指针移动得较快，并将慢指针更新为当前字符的上一个出现位置的索引。
示例
import java.util.*;
public class Solution{
// function to get the required substring
public static int longestSubStr(String str){
int len = str.length(); // getting the length of the string
int ans = 0; // variable to store the answer
int arr[] = new int[26]; // array to store the last index of the current character
Arrays.fill(arr, -1); // function to fill -1 at each index
int i = 0; // last pointer or slow pointer
// fast pointer, traversing over the string
for(int j = 0; j < len; j++){
// updating the value of the slow pointer
i = Math.max(i, arr[str.charAt(j)-'a'] + 1);
// updating the answer
ans = Math.max(ans, j - i + 1);
// updating the index of the current character
arr[str.charAt(j) - 'a'] = j;
}
return ans; // return the final answer
}
// main function
public static void main(String []args){
String str = "thisisthegivenstring"; // given string
// calling to the function
int ans = longestSubStr(str);
// print the final answer
System.out.println("The length of the longest substring that contains only unique characters is: " + ans );
}
}
输出
The length of the longest substring that contains only unique characters is: 8
时间复杂度与空间复杂度
上述代码的时间复杂度是O(N)，其中N是给定字符串的长度。
上述代码的空间复杂度是常数或O(1)，因为我们在这里没有使用额外的空间。
结论
在本教程中，我们实现了一个Java程序，用于找到最长的不重复字符子串的长度。我们实现了三种方法：第一种是找到每个子串，时间复杂度为O(N^3)；第二种是使用滑动窗口，时间复杂度为O(N^2)；第三种是双指针方法。