不重复字符的最长子字符串

Question

我已提交下列O(N)号代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int currentLongest = 0, idx = 0;

        if (s.length() <= 1){ return s.length(); }

        for (int i=1; i<s.length(); i++){
            String str = s.substring(idx, i);  //substring up to current char (exclusive)
            int strLen = str.length();
            int idxOf = str.indexOf(s.charAt(i));  //check if current char is in the substring

            if (idxOf != -1){  //if contains duplicate
                if (strLen > currentLongest){
                    currentLongest = strLen;  //replace if it is the longest substring seen
                }
                idx += idxOf+1; //move front pointer after idxOf.
            }

            if (i == s.length() -1){  // if last iteration, do final check inclusive of last char
                strLen = s.substring(idx, i+1).length();
                if (strLen > currentLongest){
                    currentLongest = strLen;
                }
            }
        }
        return currentLongest;
    }
}

它通过了所有的测试用例，然而，我觉得它是一种由黑客和工作环境(即s.length() <1部分)组成的hodge podge组合。不仅如此，我不确定子字符串()和indexOf()调用是否导致性能下降，如下所示。

运行时: 11毫秒，超过71.13%的Java在线提交最长子字符串不重复字符。内存使用量:49.2MB，不到19.11%的Java提交的最长子字符串不重复字符。

要求：

给定字符串s，查找最长子字符串的长度，不重复字符。

示例1：

输入:S=“abc abc”输出: 3解释:答案是"abc"，长度为3。示例2：

输入:S= "bbbbb“输出: 1解释:答案是"b"，长度为1。示例3：

输入:S= "pwwkew“输出: 3解释:答案是"wke"，长度为3。注意，答案必须是子字符串，"pwke”是子字符串，而不是子字符串。

Answer 1

关于时间复杂度

的思考

是的，解决方案运行在O(n)时间，但仅仅是因为字母表的有限大小。

简单地改变一下，将任务从一个字符串改为一个数字数组，找出不重复数字的最长子数组，该算法将在O(n^2)时间运行。

我认为这是值得注意的，也是值得思考的。

避免不必要的计算

String::substring方法从字符范围创建一个新字符串。这需要分配内存和复制字符的范围。

避免在可以避免的情况下创建子字符串是很好的，特别是在循环中。

例如，在循环中，在每次迭代中创建一个越来越长的子字符串是浪费的。您可以使用索引以及indexOf和lastIndexOf方法。

虽然这只执行了一次，但我想调用它：

strLen = s.substring(idx，i+1).length()；

最好使用简单的数学：

strLen = i + 1 - idx;

避免特殊治疗

这是可以避免的：

如果(s.length() <= 1){返回s.length()；}

它对初始化步骤进行了简单的更改：

int currentLongest = 0, idx = 0;

for (int i=0; i<s.length(); i++){

还可以避免对最后一个字符的特殊处理，方法是始终更新currentLongest，而不仅仅是在查找重复字符时。

if (idxOf != -1) {
    if (strLen > currentLongest){
        currentLongest = strLen;
    }
    idx += idxOf+1;
} else {
    strLen = i + 1 - idx;
    if (strLen > currentLongest) {
        currentLongest = strLen;
    }
}

顺便说一句，你看到我看到的了吗？条件在if-else的两个分支中重复，并且可以安全地移出：

if (idxOf != -1) {
    idx += idxOf+1;
} else {
    strLen = i + 1 - idx;
}

if (strLen > currentLongest) {
    currentLongest = strLen;
}

请注意，这个简化的机会以前不那么明显。通过使一件事情变得简单，很多次，它会导致另一件事情可以更简单，然后另一件事情，等等。

初始化循环语句中的变量(如果在

之外不需要它们)

而不是这样：

int currentLongest = 0，idx = 0；for (int i=0；i

这样做更好：

int currentLongest = 0;

for (int i=0, idx = 0; i<s.length(); i++){

因为idx只在循环中使用。如果它是在循环语句中声明的，那么就不可能错误地在外部使用它。

使用简单的自然名

有些变量名有些复杂或含糊不清，例如：

• 在currentLongest中，术语"current“是多余的，因为代码中没有”其他类型的最长“。所以它可以是简单的longest。
• idx，基本上是序列唯一字符的开始索引。所以可能是start或left。
• strLen是一个神秘的名字。它包含一个长度，所以它可以是简单的length。
• idxOf...什么的？它是当前字符的最后一个索引，所以它可以是lastIndex。

替代实现

消除不必要的字符串副本，并从上面应用其他想法：

int longest = 0;

for (int i = 0, left = 0; i < s.length(); i++) {
    int lastIndex = s.lastIndexOf(s.charAt(i), i - 1);

    if (lastIndex >= left) {
        left = lastIndex + 1;
    } else {
        int length = i + 1 - left;
        longest = Math.max(longest, length);
    }

}
return longest;