例题１：求无序数组中最长连续子串的长度。

　　找出数组[13,5,9,3,4,5,43,2,7,5,9,10,11,12,13,24,6,17,9]中最长的连续子串。此数组中包含3,4,5和9,10,11,12,13两个连续子串，如下图所示。写段代码，求出数组中最长连续子串的长度。

　　解题思路如下：

　　(1)声明三个变量：一个存先前数值，一个存连续子串的累加计数，一个存最大计数。

　　(2)遍历数组，循环用“先前数值十1”的方式来判断数组中是否包含一个连续子串，如果连续则计数累加；若子串断裂，则把计数赋值给最大计数，其他变量重新归位。

　　程序代码：

　　运行结果：

　　练习题１：求下面数组中不连续的最大子串的长度（不包括连续元素的头和尾）。

[19,20,21,51,55,74,83,-5,-4,-3,-1,1,3,5,7,9,11,12,13]

　　例题２：求数组中出现次数超过总数一半的数。

　　一个长度为n的数组中，其中有一个数出现次数超过n//2（整除），写段程序，求出这个数。

　　解题思路分析：这题看似简单，但是找到最优解不容易。一般情况下首先会想到最笨的方法，每选一个数，遍历一次数组，复杂度为O(n²)，或者先排序再找那个数，复杂度一般为O(nlgn)，或者用哈希，时间复杂度为O(n)，空间复杂度需要看输入的数据规模，空间复杂度为O(n)。所以这些都不是最优解法。

　　先分析这个题目，设该数出现的次数为x，则x满足，

x≥n/2+1，

即

x＞n/2。①

n同时减不等式两边，不等号反转，得

n-x<n/2。②

当x满足①式时，该元素是所求元素；当x不满足②式时，该元素不是所求元素。因此需要统计相等数量作为返回结果的条件；统计不相等的数量作为更换对比值的条件。

　　步骤描述：程序从前往后遍历，设key为第一个数，key出现的次数为count（初始化为1，代表key出现了一次），不出现的次数为dcount（初始化为0）。从key的下一位（keyIndex+1）往后，如果某个数不等于key，dcount加1，缓存第一个下标（nextKeyIndex）；如果等于key，count加1。如果count大于n//2，返回这个数。如果dcount大于n//2，则说明这个key是不可能过半数的。统计已执行的count，判定是否有这样的值，如果有key取下一个数（nextKeyIndex），dcount也取nextKeyIndex（因为已有这么多不同）。再从nextKeyIndex+1开始重复以上步骤。如果剩下的要检查元素数已小于n//2，则说明没有这样的数，返回None。

　　程序代码：

　　运行结果：

　　练习题２：上例这种题的哈希法实际就统计选票法。程序和结果如下，请在需要填写代码的地方填上代码，使它运行得到正确的结果。

　　例题３：环路加油站问题。

　　环路上有n个加油站，每一个加油站储油量为gas[i]，一辆汽车从第i个加油站到第i+1个加油站的耗油量为cost[i]，问从哪个加油站出发可以走完环路（若没有任何一个节点能走完整个环路则返回-1，假设油箱容量无限制，初始时储油量为0）？

　　每个加油站的储油量：gas=[1,2,3,4,5]；从每个节点出发到下一个加油站的耗油量：cost=[3,4,5,1,2]；如下图所示。

　　解题算法分析如下：

　　(1)暴力法：从第0个加油站开始，逐个判断车加油后的油量能否支撑到下个加油站，最后能否走完全程（每个加油站的加油量－耗油量，累加比较)，若不能，继续判断下一个节点。

　　(2)区间法：声明一个长度为n的差值数组，把每个节点的储油量与耗油量的差值全放进这个数组。然后声明一个起点游标初始化指向数组下标0，并开始从此位置向后遍历。另声明一个变量sumD代表差值和，在遍历过程中累加各个节点的差值。一旦有负数，起点游标立刻移动到此节点的下一节点，重新开始遍历。遍历位置从起点游标经过所有节点（如果超过下标，转到数组0下标)，如果遍历完成，各个加油站之间加油量减去耗油量的差值和大于或等于0，则此起点游标位置就是所求节点。

　　此处采用区间法解题，如下图所示。

　　从起点开始向后旋转累加diff(=储油量-耗油量)，当diff和小于0时，则把下一节点设为新的起点，直到转完一圈后diff和大于或等于0，则此节点为可以走完全程的起始节点。

　　程序代码：

　　运行结果：

　　例题３：像上例，站点少，数量也小，可以用暴力法。代码和运行结果如下，请完成需要填写代码的地方。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社