首页 > 代码库 > Longest Substring Without Repeating Charactersdf
Longest Substring Without Repeating Charactersdf
首先呢 可能会想到用一个windows去放这些东西.
可能会想到hashtable去. 但是hashtable 无法用Index去查询.
abcabcbb. hashtable: abc 当第二个a来的时候, 我们想bca 貌似不好实现.
这种情况就很像LRU. 用 node<prev,next>连接，用hashtable<key,node>去记录位置.
这就很麻烦了,有没有别的选择呢？
字符反而比integer的这种类型题要简单，因为最多就256种可能性. 可以看成有限制的integer类型题.所以不要心存恐惧啦.
you would need two indices to record the head and the tail of the current substring. 两个index完美的window.
Ok.所以我们需要two index完成window. c[256]记录location.
public class Solution {public int lengthOfLongestSubstring(String s) { // Start typing your Java solution below // DO NOT write main() function int length = s.length(); if (length == 0) { return 0; } int [] countTable = new int[256]; Arrays.fill(countTable, -1); int max = 1; int start = 0; int end = 1; countTable[s.charAt(0)] = 0; while (end < length) { //Has not reached a duplicate char if (countTable[s.charAt(end)] >= start) { start = countTable[s.charAt(end)] + 1; } max = Math.max(max, end - start + 1); countTable[s.charAt(end)] = end; end++; } return max; }}
Longest Substring Without Repeating Charactersdf
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。