LeetCode第三题---Longest Substring Without Repeating Characters （c++）

每周坚持刷博客，天道酬勤，加油，共勉！
题目：
Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: “pwwkew”
Output: 3
Explanation: 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.

解法一：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int location[256];
        memset(location,-1,sizeof(location));//全部赋值为-1；
        int startPosition = -1;记录初始位置
        int max = 0;//最大长度
        for(int i = 0;i<s.length();i++)
        {
            if(location[s[i]] > startPosition)//这句话意思是s[i]出现过，即将当前下标赋值给初始位置
            {
                startPosition = location[s[i]];
            }
            
            if(i-startPosition > max)
            {
                max = i - startPosition;//计算最大子串长度
            }
            location[s[i]] = i;//更新位置信息
        }
        return max;
    }
};

解法二：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLength = 0,count[128] = {0},i,j;
        for(i=0,j=0;i<s.length();i++)
        {
            if(count[s[i]] == 1)
            {
                maxLength = max(maxLength,i-j);
                while(s[i] != s[j])
                {
                    count[s[j]] = 0;
                    j++;
                }
                j++;
            }
            else
            {
                count[s[i]] = 1;
            }
        }
        return max(maxLength,i-j);
    }
};

总结：二种解法核心思想是类似的，即使用数组记录字符串string字符出现的位置，以此来判断字符串是否重复，避免使用暴力的解法，反复进行遍历，造成性能低下。
解法一：将数组256全部初始化为1，损耗了性能；解法二：只记录所需位置信息，故性能较解法一优越许多；
每天学习一点，终将水滴石穿。