咕咕咕，又更新算法辣 🌴
这次是网络工程中常用的算法-> 滑窗算法(Sliding Window)
这次解题终于没有卡顿了，从拿到题目到解出来一共花了1个小时… 🐕 好像还是挺慢的，但比之前好很多了！！！(●’◡’●)ﾉ

题目： 两数相加

题干:

Given a string, find the length of the longest substring without repeating characters.

中文翻译：

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

Example1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

Example2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

Example3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路

分析完题目后，有了一点小头绪 -> 每次在主串取一个字符时 检查该字符是否在字串中，如果在则将字串从头开始删除，直至该字符不在字串中。
由此我们可以得到这样一个流程图：

1
2
3
4
5
6
7
8
9
10
11
12
st=>start: 从主串中取一个字符,命名为变量x
cond=>condition: x是否在子串中？
in_op=>operation: 删除字串第一个元素
ag_cond=>condition: 再次判断x是否在字串中
end_op=>operation: 添加x到字串中
end=>end: 记录长度

st->cond
cond(no)->end_op->end
cond(yes)->in_op->ag_cond
ag_cond(yes)->in_op
ag_cond(no)->end_op->end

当然，这只是个初步都构思。很多步骤都可以优化，但有了大概思路，就开始动手尝试解题，我目前习惯先把题目解出来，再根据具体步骤来做优化改进。

第一种解法

我将这种算法称为暴力法，个人感觉这样解比较生硬但却又与滑窗沾边。
具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
re_s = []
max_len = 0 
# 将字符串s中的每个元素遍历取出
for temp_c in s:
    if(temp_c not in re_s):
        re_s.append(temp_c)
    elif(temp_c in re_s):
        target = 0 # 标志位
        # 取出来的元素在 子串中
        # 将子串从头开始一个一个删除
        # 并且重新判断
        while(target != 1):
            pop_c = re_s.pop(0)
            if(temp_c not in re_s):
                re_s.append(temp_c)
                target = 1
    if(len(re_s) > max_len):
        max_len = len(re_s)
return max_len

优化改进后的解法

初步解出来后，则对多余的步骤进行优化精简。
简化后的流程图：

1
2
3
4
5
6
7
8
9
10
st=>start: 从主串中取一个字符,命名为变量x
cond=>condition: x是否在子串中？
in_op=>operation: 取重复位后面的字符串
end_op=>operation: 添加x到子串中
end=>end: 与max_len比较长度，记录最长值

st->cond
cond(yes)->in_op->end_op
cond(no)->end_op
end_op->end

如果还是看不懂，可以试试看代码注释，应该挺清楚的，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 初始化子串和最大长度
temp = ""
max_len = 0
for i in s:
    if i not in temp:
        temp = temp + i
        # 只有在增加长度时才有可能使子串增长
        # 所有只在此比较长度并记录
        if len(temp) > max_len:
            max_len = len(temp)
    else:
        # 利用python的切片，取重复位后的字符串
        temp = temp[temp.index(i) + 1: ] + i
return max_len