警惕数组下标越界问题

编程那点事

不同语言对数组下标越界处理方式不一样,c语言下标越界可能会访问到不期望的数据,java则会抛出异常,ruby正向越界返回nil,负下标返回倒数n个元素。

比如在leetcode 寻找最长回文子字符串的问题中,最开始没有对下标idx1 - offset >= 0做限定,比如'cccc',字符串,左下标为-1,右下标为3,都为c,判断为相等,出现了bug

# @param {String} s
# @return {String}
def longest_palindrome(s)
    return s if s.length <= 1
    max_leng_str = ''
    target_index1 = [] # 奇数对称
    target_index2 = [] # 偶数对称
    s.length.times do |i|
        target_index2 << i if s[i] == s[i + 1]
        target_index1 << i + 1 if s[i] == s[i + 2]
    end
    target_index1.each do |idx1|
        offset = 1        
        left = s[idx1 - offset]
        right = s[idx1 + offset]
        while idx1 - offset >= 0 && left == right # 右下标大于最大长度,一定为nil,不用做右下标判断
            max_leng_str = s[(idx1 - offset)..(idx1 + offset)] if offset * 2 + 1 > max_leng_str.length
            offset += 1
            left = s[idx1 - offset]
            right = s[idx1 + offset]
        end

    end
    target_index2.each do |idx1|
        offset = 1        
        left = s[idx1 - offset + 1]
        right = s[idx1 + offset]
        while idx1 - offset + 1 >= 0 && right && (left == right) # 右下标大于最大长度,一定为nil,不用做右下标判断
            max_leng_str = s[(idx1 - offset + 1)..(idx1 + offset)] if offset * 2 > max_leng_str.length
            offset += 1
            left = s[idx1 - offset + 1]
            right = s[idx1 + offset]
        end

    end
    max_leng_str = s[0] if max_leng_str.empty?
    max_leng_str
end

发表于 2021.05.07