Ruby基于bsearch实现两数之和算法的条件判断逻辑疑问
问题解答:Ruby两数之和算法中条件判断的逻辑说明
核心原因是Array#bsearch_index方法在找不到匹配元素时会返回nil,而Ruby中nil和整数做!=比较的结果永远为true,如果省略match_idx的前置判断会导致逻辑完全错误。
具体逻辑拆分如下:
bsearch_index的返回规则:当数组中不存在符合匹配条件的元素时,该方法返回nil而非数字索引,nil在Ruby的布尔判断中属于假值。- 如果直接写
match_idx != i作为判断条件:当找不到匹配元素时,match_idx为nil,此时nil != 任意整数的结果都是true,会导致函数错误提前返回true,完全不符合算法要求。
举你给出的测试用例说明:
测试用例为arr = [0, 1, 5, 7],target = 10的场景:
第一次遍历元素0、索引i=0时,要找的匹配值是10 - 0 = 10,数组中不存在10,所以match_idx = nil。如果判断条件是match_idx != i,此时nil != 0返回true,函数会错误返回true,和预期的返回false不符。
- 加上
match_idx &&的作用就是先过滤掉nil的无效情况:只有当match_idx确实是找到的有效索引(布尔真值)时,才会继续判断该索引是否不等于当前元素的索引i。后面match_idx != i的判断是为了排除「自己和自己相加等于目标值」的无效场景,比如数组为[3,2,4]、目标值为6的场景,如果匹配到的是当前元素自身的索引,就不算有效结果。
内容的提问来源于stack exchange,提问作者hematopoietic
相关产品推荐
相关产品推荐

