LeetCode-003.Longest Substring Without Repeating Characters

题目描述：

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.

思路：

用$i,j$从$i=0,j=0$开始在字符串上划出区间，用$k$从区间$[i, j)$扫描，每扫描一次，$j$向后移动1步。不断对比$s[k]$和$s[j]$，当$s[k]$和$s[j]$相等，说明出现重复字符，则将$i$移动到$k+1$的位置，$k$再在区间$[i, j)$上重新扫描，直到$j$到达字符串末尾，于是就将所有的substring都扫描过一遍了，选出其中长度最长的即为结果。
注意： strlen() 函数时间复杂度为$O(len)$，用变量$n$保存以备后面多次使用该值，提高效率，之前没注意这个，LeetCode好几次判Time Limit Exceeded。

C语言解法：

int lengthOfLongestSubstring(char* s) {
    int j, k, i = 0;
    int len = 1, count = 1;
    int n = strlen(s);
    if(n > 1){
        for(j=i+1; j<n; j++){
            for(k=i; k<j; k++){
                if(s[j] == s[k]){
                    i = k + 1;
                    break;
                } else {
                    count++;
                }
            }
            if(len < count){
                len = count;
            }
            count = 1;
        }
    } else if(n == 0){
        len = 0;
    }
    return len;
}

C++解法：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int j, k, i = 0;
        int len = 1, count = 1;
        if(s.length() > 1){
            for(j=i+1; j<s.length(); j++){
                for(k=i; k<j; k++){
                    if(s[j] == s[k]){
                        i = k + 1;
                        break;
                    } else {
                        count++;
                    }
                }
                if(len < count){
                    len = count;
                }
                count = 1;
            }
        } else if(s.length() == 0){
            len = 0;
        }
        return len;
    }
};