如何高效对齐存在子集关系的两个lists/vectors，适配C++矩阵切片标签处理

根据问题描述，矩阵切片对应的标签子集必然是全量标签列表中的连续段，且所有标签唯一，因此可以按需选择两种实现方案：

• 单次查询场景：优先选择无额外空间的遍历查找方案，时间复杂度O(N)（N为全量列表长度），空间复杂度O(1)
• 多次查询同一全量列表场景：提前构建全量列表的「值-索引」哈希映射，预处理时间O(N)，后续每次查询时间O(1)，空间复杂度O(N)

import unittest
from typing import List, Tuple 

def doAlignment(list1: List[int], list2: List[int]) -> Tuple[int, int]:
    # 查找子集首元素在全量列表的位置
    first = list1.index(list2[0])
    # 连续切片的尾索引=首索引+子集长度-1
    last = first + len(list2) - 1
    # 可选健壮性校验：确认连续段匹配，题目保证合法可省略
    # assert list1[first:last+1] == list2, "子集不是全量列表的连续段"
    return first, last

# 列表中元素均为标签，因此都是唯一的，不会出现 [5, 5, 6, 7, 8] 这类情况
class AlignTests(unittest.TestCase):
    
    def test1(self):
        v1 = [1, 2, 3, 4, 5, 6]
        v2 = [1, 2]
        first, last = doAlignment(v1, v2)
        self.assertEqual((0, 1), (first, last))
        
    def test2(self):
        v1 = [1, 2, 3, 4, 5, 6]
        v2 = [2, 3, 4]
        first, last = doAlignment(v1, v2)
        self.assertEqual((1, 3), (first, last))

    def test3(self):
        v1 = [7, 3, 4, 6, 9]
        v2 = [3, 4, 6]
        first, last = doAlignment(v1, v2)
        self.assertEqual((1, 3), (first, last))
        
    def test4(self):
        v1 = [7, 3, 4, 6, 9]
        v2 = [3, 4, 6, 9]
        first, last = doAlignment(v1, v2)
        self.assertEqual((1, 4), (first, last))

if __name__ == '__main__':
    unittest.main()

以上代码所有测试用例100%通过。

单次查询版本（无额外空间） #

#include <vector>
#include <algorithm>
#include <utility>

std::pair<int, int> doAlignment(const std::vector<int>& full_list, const std::vector<int>& sub_list) {
    auto start_it = std::find(full_list.begin(), full_list.end(), sub_list[0]);
    int first_idx = std::distance(full_list.begin(), start_it);
    int last_idx = first_idx + sub_list.size() - 1;
    return {first_idx, last_idx};
}

多次查询版本（预构建哈希索引，查询效率更高） #

#include <vector>
#include <unordered_map>
#include <utility>

// 预处理函数：全量列表不变的情况下仅需调用一次
std::unordered_map<int, int> build_index_map(const std::vector<int>& full_list) {
    std::unordered_map<int, int> idx_map;
    for (int i = 0; i < full_list.size(); ++i) {
        idx_map[full_list[i]] = i;
    }
    return idx_map;
}

// 对齐函数：每次切片查询调用，时间复杂度O(1)
std::pair<int, int> doAlignment(const std::unordered_map<int, int>& idx_map, const std::vector<int>& sub_list) {
    int first_idx = idx_map.at(sub_list[0]);
    int last_idx = first_idx + sub_list.size() - 1;
    // 可选校验：确认尾索引匹配，避免非连续段输入
    // assert(idx_map.at(sub_list.back()) == last_idx);
    return {first_idx, last_idx};
}

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