字符串中找最长连续数字串（含正负号）的三语言实现与边界解析

“在字符串中找出连续最长的数字串含“-”号”这道题我见过太多次了。笔试里它是常见的百分配置题面试里它经常被拿来考察字符串处理和边界思维。我第一次做的时候以为就是简单地把连续数字收集起来比长度结果被“正负号到底算不算数字串的一部分”这个问题狠狠上了一课。这周正好有个读者问起我干脆把 Java、JavaScript、Python 三种语言的完整实现和踩坑过程都梳理一遍给准备笔试面试的朋友做个参考。题目本身不难但分很容易丢。丢分点集中在几个地方正负号算不算数字串的一员、正负号独立出现怎么处理、连续出现两个符号时该从哪个位置开始找、多个同样长的数字串该返回哪一个。这些问题想不清楚代码写得再快也会在评测用例上翻车。下面我会先建一个统一的边界判断模型再分别给出三种语言的实现最后用一组实测用例验证。1. 这道题真正难住人的地方数字串的“边界”定义1.1 大多数人拿到题会怎么想先描述一下大多数人的第一反应从头到尾遍历字符串遇到数字就收集遇到非数字就断开比一下长度留下最长的。这种思路解决“纯数字串”没问题一旦题目加上“含正负号”立刻出现三个新问题。第一个问题正负号出现在字符串里时到底算不算数字串的一部分比如abc123def如果按“遇到非数字就断开”的规则是非数字那结果就是123长度为 3。但如果正负号算数字串的一部分结果应该是123长度为 4。题目描述里写了“含正负号”那么123才是符合题意的答案。第二个问题正负号必须是数字串的开头那如果符号前面就是数字比如123456正负号是断点还是继续按我的理解123是一段合法数字串456是另一段合法数字串因为它们各自都满足“可选正负号 连续数字”的结构。所以最长结果是456长度 4而不是把123456整个当成数字串。第三个问题正负号后面不跟数字怎么办比如abcdef单独一个不能算数字串因为它缺少数字部分长度为零的“空数字串”通常不计入比较。这三个问题本质上是同一个你没有先把“合法数字串”的边界定义清楚。1.2 “含正负号”不是把符号无脑拼进去我找一个比较直观的说法一个合法的“含正负号的数字串”形式化定义是——以可选的或-开头后面紧跟至少一位数字再后面全是数字。这里的核心约束有两个正负号最多只能出现一个而且必须是这个数字串的第一个字符。正负号后面必须紧跟数字否则这个符号不能作为任何数字串的开头。把这两个约束拆开就能解释很多看起来模糊的用例。a--123b怎么处理第一个-后面跟的是第二个-不是数字所以第一个-不能作为合法数字串的开头跳过。第二个-后面跟的是1合法于是从第二个-开始得到-123长度 4。--123整体不能作为数字串因为数字串不包含“两个连续符号”这种结构。a-123b同理。后面是-不是数字跳过-后面是1合法得到-123。123456呢扫描到1进入数字收集收集到123。继续扫描遇到看看它后面紧跟的是4是数字所以可以作为新一段数字串的开头于是再从开始收集得到456。两段长度分别是 3 和 4答案取456。如果123x456前面是x但正负号前面的字符是什么根本不影响判断只要正负号后面的字符是数字它就能作为新数字串的开头。这跟直觉习惯有点不一样但按题目规则完全说得通。1.3 一个统一的判断模型合法开头与合法数字为了让代码不纠结我把判断抽象成两个东西。合法开头valid start当前位置是一个数字或者当前位置是/-且下一个位置是数字。数字digit字符在0到9之间ASCII 数字。遇到合法开头时记录当前位置为这段数字串的起点。如果当前是符号指针先往后挪一位跳过符号然后持续向后收集数字直到遇到非数字为止。这样就得到一段候选数字串。遇到不满足合法开头的字符直接跳过。这里有个容易忽略的点如果当前位置是符号但后面不是数字当前符号要跳过如果跳过去之后下一个位置恰好也是符号且后面是数字那它就是合法开头照常处理。这个模型用生活类比来说正负号像门牌号数字是房子。门牌号只有挂在房子前面才有意义光有门牌号没有房子不算一个地址出现“连续两个门牌号”时只有紧挨着房子那一个有效。2. 先写通解基于指针扫描的 O(n) 算法骨架2.1 状态设计与遍历规则先把手写解法的状态定义清楚后面三种语言都按照同一个骨架来写避免各写各的导致逻辑不一致。需要维护四个变量n字符串长度i扫描指针用于遍历每个字符start当前这段合法数字串的起点下标maxStart当前发现的最长数字串起点下标maxLen当前发现的最长数字串长度遍历规则如下while i n: 当前字符 s[i] 如果 当前字符是数字: start i 不断向后收集数字直到遇到非数字 得到一段数字串 更新最大长度 否则如果 当前字符是 或 - 且 i 1 n 且 s[i 1] 是数字: start i i i 1 // 跳过符号 不断向后收集数字直到遇到非数字 得到一段带符号数字串 更新最大长度 否则: i i 1注意一点上面“不断向后收集数字”的循环结束时i指向的是第一个非数字字符。外层循环不需要额外i因为内层循环已经让i停在了正确的位置。如果没有走到任何内层循环才需要手动i。这个结构看起来简单但它把两个关键判断都覆盖了符号后必须紧跟数字符号本身不参与数字收集。2.2 记录方式起点、长度、最大值为什么不直接在扫描过程中用 substring 把每段截出来原因是频繁创建子串会带来不必要的内存开销尤其是字符串很长的时候。记录起点和长度到最后统一截取一次空间复杂度是 O(1)不计输出字符串实现也更优雅。更新最大值的规则也有讲究。题目通常要求“连续最长的数字串”如果没有特别说明一般认为多个等长候选时返回第一个。更新条件用curLen maxLen而不是curLen maxLen就可以保证保留第一次发现的最长串。初始值方面maxLen设为 0maxStart设为 -1。扫描结束如果maxStart还是 -1说明整个字符串里不存在合法数字串返回空字符串。2.3 复杂度与正确性分析时间复杂度是 O(n)。每个字符最多被访问两次一次从外层进入判断是否为合法开头另一次在内层数字收集循环中被消费。符号字符只会在跳过符号时被访问一次不会重复进入数字收集。整体线性。空间复杂度是 O(1)除去返回的字符串只用了固定几个整型变量。正确性可以从“合法数字串必然从一个合法开头开始”来理解。任意一段合法的数字串它的第一个字符要么是数字要么是符号且紧接着是数字这恰好就是代码里的合法开头判断。通过遍历所有合法开头并向后收集到最长连续数字就能覆盖所有可能成为候选的串。非合法开头的字符不可能作为一段合法数字串的起始位置跳过它们不会漏掉答案。3. Java JS Python 三语实现与差异3.1 Java 实现最容易在索引上栽跟头Java 里最大的坑是String.charAt(i)越界会直接抛StringIndexOutOfBoundsException。判断“下一个字符是否是数字”时必须先用i 1 n保证不越界再取字符。另一个容易踩的坑是Character.isDigit(char)。这个方法对全角数字、甚至某些 Unicode 数字字符都会返回true。如果 OJ 的测试数据里混入了全角数字用Character.isDigit会把这些字符也当成合法数字收集结果不一样。面试场合想严格限制 ASCII 数字我建议直接写c 0 c 9语义最清晰。手写遍历版本public class LongestNumericSubstring { public static String findLongest(String s) { if (s null || s.isEmpty()) { return ; } int n s.length(); int maxStart -1; int maxLen 0; int i 0; while (i n) { char c s.charAt(i); boolean isSign c || c -; boolean nextIsDigit i 1 n isAsciiDigit(s.charAt(i 1)); if (isAsciiDigit(c) || (isSign nextIsDigit)) { int start i; if (isSign) { i; } while (i n isAsciiDigit(s.charAt(i))) { i; } int curLen i - start; if (curLen maxLen) { maxLen curLen; maxStart start; } } else { i; } } return maxStart -1 ? : s.substring(maxStart, maxStart maxLen); } private static boolean isAsciiDigit(char c) { return c 0 c 9; } }如果笔试时间紧张Java 也可以用正则配合Pattern和Matcher快速实现import java.util.regex.Matcher; import java.util.regex.Pattern; public class LongestNumericSubstringRegex { public static String findLongest(String s) { Pattern pattern Pattern.compile([-]?\\d); Matcher matcher pattern.matcher(s); String result ; while (matcher.find()) { String cur matcher.group(); if (cur.length() result.length()) { result cur; } } return result; } }Java 正则里\d在默认情况下只匹配 ASCII 数字不会匹配全角数字这一点反而比Character.isDigit更符合题目默认预期。使用正则时需要注意正则表达式会按照从左到右的顺序查找子串对于123456会匹配出123和456两个候选正好符合我们的语义。3.2 JavaScript 实现字符串下标与正则的诱惑JavaScript 的字符串可以按下标读取字符这点和 Java 类似但越界时返回undefined而不是抛异常写判断时容易忽略。很多人会用isNaN判断字符是否数字这是经典的反面教材。isNaN( )返回false因为空字符串会被隐式转换成 0isNaN(12)也返回false看起来是数字但isNaN(12a)返回true。在逐字符判断时这套逻辑漏洞太多直接用字符范围比较最稳。手写版本function findLongest(s) { if (s null || s.length 0) { return ; } const n s.length; let maxStart -1; let maxLen 0; let i 0; while (i n) { const c s[i]; const isDigit c 0 c 9; const isSign c || c -; const nextChar i 1 n ? s[i 1] : ; const nextIsDigit nextChar 0 nextChar 9; if (isDigit || (isSign nextIsDigit)) { const start i; if (isSign) { i; } while (i n s[i] 0 s[i] 9) { i; } const curLen i - start; if (curLen maxLen) { maxLen curLen; maxStart start; } } else { i; } } return maxStart -1 ? : s.substring(maxStart, maxStart maxLen); }JS 的正则版本一行能搞定核心逻辑function findLongest(s) { const matches s.match(/[-]?\d/g) || []; return matches.reduce((max, cur) cur.length max.length ? cur : max, ); }String.prototype.match配合全局标志会返回所有匹配项没有匹配时返回null所以用|| []兜底。reduce里用严格大于保证多个等长候选时返回第一个。JS 正则的\d匹配 ASCII 数字这点和大多数 OJ 预期一致。3.3 Python 实现切片与 re 模块Python 代码写起来通常最舒服但有一个很隐蔽的坑str.isdigit()。这个方法对全角数字、上标数字、带圈数字等 Unicode 数字都会返回True。比如².isdigit()结果是True.isdigit()也是True。如果题目只想要 ASCII 数字用str.isdigit()会出问题。手写版本def find_longest(s: str) - str: if not s: return n len(s) max_start -1 max_len 0 i 0 def is_ascii_digit(c): return 0 c 9 while i n: c s[i] is_sign c or c - next_is_digit i 1 n and is_ascii_digit(s[i 1]) if is_ascii_digit(c) or (is_sign and next_is_digit): start i if is_sign: i 1 while i n and is_ascii_digit(s[i]): i 1 cur_len i - start if cur_len max_len: max_len cur_len max_start start else: i 1 return if max_start -1 else s[max_start:max_start max_len]Python 的re.findall版本非常简洁import re def find_longest(s: str) - str: matches re.findall(r[-]?\d, s) return max(matches, keylen, default)这里要注意一个和 Java、JS 不同的点Python 的re模块默认把\d匹配为 Unicode 数字会连全角数字一起匹配。想要严格匹配 ASCII 数字需要把正则换成[-]?[0-9]或者在正则最前面加(?a)内联标志写成(?a)[-]?\d。我一般直接写[0-9]更直白。max(matches, keylen, default)这个写法很优雅default是 Python 3.4 之后支持的参数遇到空列表时返回空字符串不需要单独判断。4. 测试用例设计与实测结果4.1 边界场景清单我把这类题常见的用例整理成了一个表直接用这组用例跑三种语言的实现。下面这个表格里期望结果按照“返回第一个最长串”的规则确定。用例编号输入字符串期望结果说明1空字符串2abc!#没有任何数字3123456123456纯连续数字4abc123def123普通无符号场景5a123b123符号后紧跟数字6ab符号后不是数字7a--123b-123连续符号只取后一个8a-123b-123两个符号第二个有效9123456456后半段带符号更长10123-456-456多条合法串选最长11-123abc456-123长度相同取第一个12abcdef全角数字按非 ASCII 数字处理第 12 个用例是全角数字这里我按“题目没有明确要求支持全角数字就默认只处理 ASCII 数字”来设计。如果你用的是Character.isDigit或 Python 的str.isdigit这个用例会失败这正好对应前面说的语言陷阱。4.2 三种实现跑同一批用例的结果手写版本用同样的判断逻辑实现三种语言在 1 到 11 号用例上输出完全一致全部通过。主要差异在第 12 号用例Java 版本如果写Character.isDigit会匹配全角数字输出长度为 3不符合表格里的期望结果改成c 0 c 9后输出。JavaScript 的c 0 c 9对全角数字返回false所以输出符合预期。JS 正则\d也不会匹配全角数字。Python 手写版本用0 c 9判断输出符合预期但如果写c.isdigit()输出。Python 正则\d同样会匹配全角数字输出要用[0-9]才符合预期。这说明一个很重要的问题不同语言对“数字字符”的默认定义不一样做这类题时不要想当然。如果你不确定平台用的字符集和测试数据优先用 ASCII 范围的比较覆盖面最可控。4.3 性能与健壮性对比我拿一段超长随机字符串做了个简单对比长度大概 100 万字符。手写遍历版本在三种语言里都是线性耗时Java 和 JS 大概几十毫秒级别Python 大概几百毫秒级别。正则版本在短字符串上很方便遇到超长字符串时匹配库本身性能也不差但创建匹配结果列表会有额外内存开销。实际笔试和面试中性能通常不是这道题的瓶颈逻辑正确才是。正则写法代码量少适合快速答题手写遍历写法更容易体现你对边界条件的理解也方便面试官顺着题目追问原理。我个人的习惯是先手写一遍再提一句“这个逻辑也可以用正则简化”展现两层能力。# 性能测试示例Python import re import time def find_longest_regex(s: str) - str: matches re.findall(r[-]?[0-9], s) return max(matches, keylen, default) if __name__ __main__: s (a123b * 200000) x-9999999y t0 time.perf_counter() result find_longest_regex(s) t1 time.perf_counter() print(result, t1 - t0)这段测试跑下来正则版本在 100 万字符级别的输入上也能在 1 秒以内返回结果说明性能上不用担心。5. 从这道题延伸出去的变体与经验5.1 变体一要求输出所有最长数字串有些版本会改成“找出所有长度等于最长值的数字串”这时就不能只保存一个maxStart了。思路是在一次遍历中收集所有候选先确定最大长度再把长度等于最大值的候选收集起来。更经济的做法是分两遍第一遍扫描出最大长度第二遍再扫描把所有长度等于最大值的子串收集起来。时间复杂度依然是 O(n)。def find_all_longest(s: str) - list: pattern re.compile(r[-]?[0-9]) matches pattern.findall(s) if not matches: return [] max_len max(len(m) for m in matches) return [m for m in matches if len(m) max_len]遇到这种变体核心逻辑没变只是结果存储方式变了。我在面试里也被问过类似问题给面试官讲清楚“两遍扫描”的思路比用复杂的单遍多容器逻辑更好懂。5.2 变体二支持小数点和科学计数法如果题目升级成“找出最长的数字串支持整数、小数和科学计数法”正则扩展一下就行# 支持小数 pattern re.compile(r[-]?[0-9](?:\.[0-9])?) # 支持科学计数法 pattern re.compile(r[-]?[0-9](?:\.[0-9])?(?:[eE][-]?[0-9])?)手写遍历的逻辑需要相应增加状态判断遇到.时要求后面至少一位数字遇到e/E时要求后面跟可选符号和至少一位数字。状态一多手写代码的复杂度明显上升所以遇到这种扩展题优先用正则更划算。不过要提醒一句如果题目没有明确说支持小数点不要自作主张去匹配小数。很多 OJ 的隐藏用例是按照最保守定义生成的你多匹配了一个.反而会错。5.3 我踩过的几个坑第一个坑全角数字陷阱。我在一次用 Python 快速写题时用了str.isdigit()结果遇到全角数字时把当成合法数字串输出了。后来养成了习惯字符串算法题里一律用0 c 9判断 ASCII 数字明确和产品需求对齐不再依赖语言内置的宽泛判断。第二个坑符号后没有数字。我早期代码里判断符号是合法开头时没有检查下一个字符是否是数字导致ab输出。这个用例看起来简单但很多人会在逻辑里漏掉“正负号后面必须跟数字”这个条件。我的建议是把“合法开头”抽象成一个单独函数每个分支都过一遍边界用例。第三个坑等长候选取最后一个。更新最大值时如果用了123-456这类用例可能输出最后一段-456而不是第一个1两者长度不同这个例子不太直观换成123456就明显了用可能输出456而不是123虽然两者长度都是 4但如果你“想要第一个”就会出错。笔试判题通常按标准答案匹配取错位置直接影响结果。第四个坑字符串为空时返回什么。有人喜欢判断s 时返回null但绝大多数题面要求返回字符串空字符串和null在判题系统里是两种完全不同的结果。建议默认返回输出也安全。5.4 我的做题建议这道题整体属于“字符串扫描 边界条件”的经典组合。解决它的关键在于先把合法数字串的定义写清楚再写代码。定义不清代码写得再快也是白搭。笔试时我的顺序是先花一分钟把用例拆清楚特别是含正负号的用例然后手写遍历版本最后如果时间充裕再补一句“也可以用正则在 O(n) 内解决”。面试时如果面试官只让你说思路优先讲判断合法开头的条件再把更新最大值的逻辑讲明白基本就能把分拿满。这道题我能说的就这么多。如果你也在准备笔试面试建议别只看答案自己动手把三种语言都写一遍踩过的坑记得多了考场上自然稳。