如何在不等长三层嵌套列表中通过偏移量查找元素索引？

核心思路是将三层嵌套列表的三维索引与全局线性索引建立双向映射，通过前缀和数组实现快速转换，彻底避免复杂的嵌套判断逻辑。

步骤1：预处理前缀和数组 #

提前计算两个前缀和数组，用于快速将三维索引转换为全局位置，以及反向转换：

1. 外层前缀和数组：totalElementsBeforeI，其中totalElementsBeforeI[i]表示前i个外层列表（索引0到i-1）包含的总元素数。
2. 中层前缀和数组：totalElementsBeforeJInI，其中totalElementsBeforeJInI[i][j]表示第i个外层列表中，前j个中层列表（索引0到j-1）包含的总元素数。

C# 预处理代码 #

List<List<List<string>>> elements = new()
{
    new() { new List<string>() { "E0", "E1" }, new List<string>() { "E2" } },
    new() { new List<string>() { "E3" }, new List<string>() { "E4", "E5" }, new List<string>() { "E6", "E7", "E8" } },
    new() { new List<string>() { "E9" } }
};

// 计算外层前缀和：totalElementsBeforeI[i] = 前i个外层列表的总元素数
List<int> totalElementsBeforeI = new List<int> { 0 };
int outerCumulative = 0;
foreach (var middleList in elements)
{
    outerCumulative += middleList.Sum(inner => inner.Count);
    totalElementsBeforeI.Add(outerCumulative);
}

// 计算每个外层列表对应的中层前缀和
List<List<int>> totalElementsBeforeJInI = new List<List<int>>();
foreach (var middleList in elements)
{
    List<int> innerPrefix = new List<int> { 0 };
    int middleCumulative = 0;
    foreach (var innerList in middleList)
    {
        middleCumulative += innerList.Count;
        innerPrefix.Add(middleCumulative);
    }
    totalElementsBeforeJInI.Add(innerPrefix);
}

步骤2：实现索引转换函数 #

三维索引转全局位置 #

根据前缀和数组，直接计算目标元素的全局线性位置：

int GetGlobalPosition(int i, int j, int k)
{
    // 校验索引合法性（可选）
    if (i < 0 || i >= elements.Count) throw new ArgumentOutOfRangeException(nameof(i));
    if (j < 0 || j >= elements[i].Count) throw new ArgumentOutOfRangeException(nameof(j));
    if (k < 0 || k >= elements[i][j].Count) throw new ArgumentOutOfRangeException(nameof(k));
    
    return totalElementsBeforeI[i] + totalElementsBeforeJInI[i][j] + k;
}

全局位置转三维索引 #

通过前缀和数组反向推导三维索引：

(int i, int j, int k) Get3DIndex(int globalPos)
{
    // 校验全局位置合法性（可选）
    if (globalPos < 0 || globalPos >= totalElementsBeforeI.Last()) throw new ArgumentOutOfRangeException(nameof(globalPos));
    
    // 找到对应的外层索引i
    int i = totalElementsBeforeI.FindLastIndex(x => x <= globalPos);
    int remainingAfterI = globalPos - totalElementsBeforeI[i];
    
    // 找到对应的中层索引j
    int j = totalElementsBeforeJInI[i].FindLastIndex(x => x <= remainingAfterI);
    int k = remainingAfterI - totalElementsBeforeJInI[i][j];
    
    return (i, j, k);
}

步骤3：计算偏移后的目标索引 #

以你的示例测试：已知E的索引(0,1,0)，偏移量5：

// 计算E的全局位置
int ePos = GetGlobalPosition(0, 1, 0); // 结果为2
// 计算目标位置
int targetPos = ePos + 5; // 结果为7
// 转换为三维索引
var fIndex = Get3DIndex(targetPos); // 结果为(1,2,1)，与预期一致

方案优势 #

• 避免了嵌套遍历和复杂的if/else判断，逻辑清晰易维护
• 预处理仅需一次，后续转换操作时间复杂度为O(N)（若列表规模极大，可改用二分查找将时间复杂度降至O(logN)）
• 内存占用低，仅存储前缀和数组，无需额外存储所有元素的映射关系

可选优化 #

如果嵌套列表规模极大，可将FindLastIndex替换为二分查找，进一步提升转换效率：

// 二分查找实现外层索引i
int FindOuterIndex(int globalPos)
{
    int left = 0, right = totalElementsBeforeI.Count - 1;
    int result = 0;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (totalElementsBeforeI[mid] <= globalPos)
        {
            result = mid;
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return result;
}

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