共计 3063 个字符，预计需要花费 8 分钟才能阅读完成。
这篇文章主要讲解了“Java 怎么使用指针进行搜索”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着丸趣 TV 小编的思路慢慢深入，一起来研究和学习“Java 怎么使用指针进行搜索”吧！
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given abcabcbb , the answer is abc , which the length is 3.
Given bbbbb , the answer is b , with the length of 1.
Given pwwkew , the answer is wke , with the length of 3. Note that the answer must be
a substring; pwke is a subsequence and not a substring.*package com.lifeibigdata.algorithms.leetcode;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
* Created by lifei on 16/5/27.
*
* 时间复杂度为 O(N) 的算法
使用 i 和 j 两个指针进行搜索，i 代表候选的最长子串的开头，j 代表候选的最长子串的结尾。 先假设 i 不动，那么在理想的情况下，我们希望可以一直右移 j，直到 j 到达原字符串的结尾，此时 j - i 就构成了一个候选的最长子串。每次都维护一个 max_length，就可以选出最长子串了。 实际情况是，不一定可以一直右移 j，如果字符 j 已经重复出现过（假设 i 在位置 k），就需要停止右移了。记录当前的候选子串并和 max_length 做比较。接下来为下一次搜寻做准备。 在下一次搜寻中，i 应该更新到 k +1。这句话的意思是，用这个例子来理解，abcdef 是个不重复的子串，abcdefc 中（为了方便记录为 abc1defc2）,c1 和 c2 重复了。 那么下一次搜寻，应该跨过出现重复的地方进行，否则找出来的候选串依然有重复字符，且长度还不如上次的搜索。所以下一次搜索，直接从 c1 的下一个字符 d 开始进行， 也就是说，下一次搜寻中，i 应该更新到 k +1
*/
public class LengthOfLongestSubstring { public static void main(String[] args) { LengthOfLongestSubstring lols = new LengthOfLongestSubstring();
System.out.println(lols.lengthOfLongestSubstring( abcdefcgh));
}
public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j n; ++j) { i = Math.max(index[s.charAt(j)], i);//index[a] 会将 char 转为 ascII 码,a 是 97
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1; // 将 j 所在的值, 的对应位置存到 index 数组中
}
return ans;
}
// public int lengthOfLongestSubstring(String s) {// int n = s.length();
// Set Character set = new HashSet ();
// int ans = 0, i = 0, j = 0;
// while (i n j n) {// // try to extend the range [i, j]
// if (!set.contains(s.charAt(j))){ // 如果 j 没有出现重复字符, 将 j 添加到 set 中, 这个过程中,i 保持不变
// set.add(s.charAt(j++));
// ans = Math.max(ans, j - i); // 比较获取最大的 ans
// }
// else { // 出现重复字符, 这个字符在 i - j 之间, 所以从 i 开始逐个删除, 直到不包含重复字符
// set.remove(s.charAt(i++));
// }
// }
// return ans;
// }
// public int lengthOfLongestSubstring(String s) { // 使用 map 存储字母和索引
// int n = s.length(), ans = 0;
// Map Character, Integer map = new HashMap (); // current index of character
// // try to extend the range [i, j]
// for (int j = 0, i = 0; j n; ++j) {// if (map.containsKey(s.charAt(j))) {// i = Math.max(map.get(s.charAt(j)), i);
// }
// ans = Math.max(ans, j - i + 1);
// map.put(s.charAt(j), j + 1);
// }
// return ans;
// }
// public int lengthOfLongestSubstring(String s) {// int n = s.length();
// int ans = 0;
// for (int i = 0; i n; ++i)
// for (int j = i + 1; j = n; ++j)
// if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
// return ans;
// }
// public boolean allUnique(String s, int start, int end) {// Set Character set = new HashSet ();
// for (int i = start; i end; ++i) {// Character ch = s.charAt(i);
// if (set.contains(ch)) return false;
// set.add(ch);
// }
// return true;
// }
}感谢各位的阅读，以上就是“Java 怎么使用指针进行搜索”的内容了，经过本文的学习后，相信大家对 Java 怎么使用指针进行搜索这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是丸趣 TV，丸趣 TV 小编将为大家推送更多相关知识点的文章，欢迎关注！
正文完
