查找字符串数组拼接后第n位字符对应的原数组成员索引

问题背景 #

现有如下字符串数组：[ "one", "two", "three" ]。
给定索引参数n，需要完成的逻辑为：将数组内所有字符串按顺序拼接为一个完整字符串后（示例数组拼接结果为"onetwothree"），找出完整字符串中索引为n的字符所属的原数组元素的下标值。
举个例子：

• n=2时对应字符为"e"
• n=3时对应字符为"t"
• n=4时对应字符为"w"

示例数组的输入输出对应关系如下：

实现思路 #

不需要实际拼接整个数组（数组规模大时可以节省内存开销），只要遍历数组累加每个元素的长度，直到累加长度覆盖目标索引即可，具体逻辑：

1. 初始化累加长度变量current_total = 0
2. 按下标顺序遍历原数组：
   • 若current_total + 当前元素长度 > n，说明目标字符落在当前元素区间内，直接返回当前元素下标
   • 否则将当前元素长度加到current_total中，继续遍历下一个元素
3. 可提前补充边界校验：如果n小于0或者大于等于所有字符串总长度，返回异常标识即可

代码示例（Python版） #

def find_original_index(arr: list[str], n: int) -> int:
    current_total = 0
    for idx, s in enumerate(arr):
        s_len = len(s)
        if current_total + s_len > n:
            return idx
        current_total += s_len
    # 触发该分支说明n超出拼接字符串总长度范围
    raise ValueError("索引n超出有效范围")

# 示例测试
test_arr = ["one", "two", "three"]
print(find_original_index(test_arr, 2))  # 输出0
print(find_original_index(test_arr, 3))  # 输出1
print(find_original_index(test_arr, 4))  # 输出1
print(find_original_index(test_arr, 9))  # 输出2

内容的提问来源于stack exchange，提问作者Berliner95