[数据结构与算法]LeetCode笔记-03-无重复字符的最长子串

解题

第一次的解题思路

1.记录不重复的字符以及对应的小标，这里使用了map<char,short> record_str记录；
2.当record_str中有当前遍历到的字符时，获取对应的item_ptr的second下标，计算当前下标与second下标的距离与max_len；
3.如果record_str中没有当前遍历到的字符时，判断max_len与record_str内的个数+1，更新max_len；将当前遍历到的字符和下标放到record_str中；
代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) {
            return 0;
        }
        map<char, short> record_str;
        int max_len = 0;
        int record_pos = 0;
        map<char, short>::iterator item_ptr;
        for (size_t i = 0; i < s.size(); i++) {
           auto it = s.at(i);
		   if ((item_ptr = record_str.find(it)) != record_str.end()) {
               int dif = i - item_ptr->second;
               if (dif > max_len) {
                   max_len = dif;
               }
               int last_pos = item_ptr->second;
               for (int j = record_pos; j <= last_pos; ++j) {
                   record_str.erase(s.at(j));                   
               }
               record_pos = last_pos + 1;
           }
           else {
			   if (max_len < record_str.size() + 1) {
                   max_len = record_str.size() + 1;
               }
           }
           record_str.insert(make_pair(it, i));
        }
        
        return max_len;
    }
};

这里陷入思路上的误区，第一使用map<char,short>并没有错，一开始我也想到使用map来记录更新，不作为不重复字符的个数的依据；就因为使用了map的size来作为不重复字符的个数，所以就需要对map进行频繁的删除和插入。插入稍微好点，删除时，会删除从当前无重复字符串的开始到当前重复字符下标内的所有字符都要从map中删除，这样一来性能就下降了；

第二次的解题思路

1.记录了无重复子串的开始位置pre_pos；
2.定义128字符的数组map_list，对照ASCII表的值，初始每个字符的下标为0；
3.更新pre_pos的位置为max(pre_pos, map_list[s[i]])，更新map_list中字符对应的下标位置为当前下标+1；
4.计算max_len为当前下标减去开始位置+1；

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) {
            return 0;
        }

        int map_list[128] = { 0 };
        int max_len = 0;
		int pre_pos = 0;
		for (int i = 0; i < s.size(); i++) {
			pre_pos = max(pre_pos, map_list[s[i]]);
			map_list[s[i]] = i + 1;
			max_len = max(max_len, i - pre_pos + 1);
		}
        return max_len;
    }
};

需要注意的是：我开始更新map_list中字符对应的下标位置为当前下标，在过用例时，对" "不通过；因为i - pre_pos为0；