面试编程题解题思路（一）

0x01 关于匹配字符串的最大长度问题

 这类问题主要考虑采用动态滑框的方式

1. 寻找字符串中无重复字符的最长子串长度

    字符串 s1 = ‘abcc’ 最长的子串为 ‘abc’   此时在后面加上字符 ‘d’， 变成字符串 s2 = ‘abccd’

    要寻找s2的最大长度就要比较原本的 s1的最长串‘abc’， 以及加入新字母后的字符串长度‘ cd’ 挑选长的代替 可见还是原本的s1为最长串

    所以寻找最长串的动态滑框可以理解为 在原有字符串上依次添加字母，然后与原有的串进行比对。代码如下

def find_max(s):

    if s = '':
       return 0
    if len(s) == 1:
       return 1

    length = 0
    
    for i in range(0, len(s)):
        length = max(length, find_left(s, i)
    
    return length

首先排除特殊情况空串和只有一个字符的情况，随后对字符串s进行依次遍历，寻找最大串长度。

2. 寻找串中不重复字符的串长度

在寻找最大长度时采用从右向左的方式扫描字符串，代码如下

def find_left(s, i):
    tmp = s[i]
    j = i-1

    while j >= 0 and s[j] not in s:
        tmp = tmp + s[j]
        j = j - 1
    
    return len(tmp)

0x02 二分查找

看到复杂度要求为O(nlong(m)) 首先考虑二分查找

二分查找思想：

python中查找中位数的小技巧：

def find_mid(num):
    half = len(num)//2
    return (num[helf] + num[~half])/2

~half 表示负索引，即数列 [1,2,3,4,5,6]  2的索引为1  那~2的索引为 -（1+1）=-2