Question

找出字符串中的最长连续数字子串

Answer 1

对于这道题目，首先我们需要进一步缩小题目范围。题目中并没有给出字符串中的数字都是什么数字。比如是否包含负数，是否包含小数等。因此简单起见，我们假设该输入字符串中只包含正整数。且假设输入字符串中没有空格。

设输入字符串的长度为 n 。

从Best Conceivable Time的角度考虑，这道题的时间复杂度至少为 O(n) 。也就是说，对于这道题而言，我们至少需要遍历整个输入的字符串一次才能得出答案。因此在时间复杂度角度考虑，我们并没有多少优化的空间。

从空间复杂度的角度考虑，brute-force解法比较直观，就是遍历一遍整个输入字符串，找出并记录其中所有的连续数字子串。然后在所有被记录的数字子串中找出最长的那个。因为题目要求有多个最长子串时返回最后一个，所以我们只需要返回最后一个被记录的最长子串即可。这个方法最坏情况下需要记录整个输入字符串。所以空间复杂度为 O(n) 。

具体实现如下：

但事实上，考虑到我们需要的只是子字符串的起始index和长度，这道题可以用2 pointers的方法解决。并不需要记录中间产生的任何子字符串。这样的话我们可以将算法的空间复杂度降到 O(1) 。

具体算法为：从头到尾遍历字符串，每当遇到数字连续数字子串时，记录其长度。并与全局记录的最长长度相比较。如果更长的话，就记录当前长度和开始index。

实现如下：