pwke",是子序列,而不是子串
"滑动窗口法"优化解决
使用暴力法解决是非常简单,但是在暴力法中我们会反复检查一个子字符串是否含有重复的字符.但其实没有这个必要....,我们将[i,j)向右滑动1个元素,则它将变成[i+1,j+1)(左闭,右开);
思路
如果从索引i到j-1之间的子字符串S[ij]已经被检查为没有重复字符.那则只需要检查s[j]对应的字符是否存在于子字符串...s[ij];
由于在C语言中是没有集合这一个概念的.所以我们使用java来实现.我们可以通过HashSet作为活动窗口.那我们只需要用O(1)的时间来完成对字符是否在当前子字符串的检查....我们使用HashSet将字符存储在当前窗口[i,j),最初i=j .然后我们向右侧滑动索引j,如果它不在HashSet中,则我们会继续滑动j.直到s[j]已经存在于HashSet中,此时,我们就已经找到的没有重复字符的最长子串将会以索引...实现
Java Code
复杂度分析
时间复杂度: o(2n) = o(n);在最糟糕的情况下,每个字符顶多被i,j访问2次.