已知index_a时求解耦合数组等式的未知索引index_b、index_c

这个问题本质是离散值匹配问题，不适合用连续域的线性代数求解器，按约束分层拆解+哈希查表的方案可以在O(n)时间复杂度下拿到所有合法解，步骤如下：

求解步骤 #

• 第一步：优先求解所有合法的index_b候选
  已知index_a的前提下，第一个约束等式仅存在index_b一个未知量，直接移项得到目标匹配值：
  target_b = array2[index_a] - array1[index_a]
  所有满足array1[i] == target_b的索引i，就是全部合法的index_b候选。如果这一步找不到匹配值，直接判定无合法解，无需进入后续步骤。
  为了避免每次遍历全数组，可以提前构建array1的「值-索引列表」哈希映射，查询时间可以从O(n)降到O(1)。

• 第二步：基于index_b候选匹配合法index_c
  对每个确定的index_b，第二个约束等式仅存在index_c一个未知量，移项整理得到目标匹配差值：
  target_c_diff = array2[index_b]
  所有满足array1[j] - array2[j] == target_c_diff的索引j，就是对应当前index_b的合法index_c取值。
  这一步同样可以提前预处理，构建「array1[j]-array2[j]差值-索引列表」的哈希映射，实现O(1)查询。

注意事项 #

• 如果数组存储的是浮点数，不要直接用==判断相等，需要设置极小的误差阈值（比如1e-9），两个值的差的绝对值小于阈值即判定匹配，避免浮点数精度误差导致漏解。
• 如果数组存在重复值，哈希映射的value需要存储对应值的全部索引，避免漏掉合法解。
• index_c需要同时是array1和array2的合法索引，预处理时遍历范围取两个数组长度的最小值即可。

参考实现（Python） #

from collections import defaultdict

def find_valid_index_pairs(array1, array2, index_a):
    # 预处理构建两个哈希映射，加速查询
    val_to_b = defaultdict(list)
    diff_to_c = defaultdict(list)
    len1, len2 = len(array1), len(array2)
    for idx in range(len1):
        val_to_b[array1[idx]].append(idx)
    # index_c需要同时在两个数组的合法索引范围内
    for idx in range(min(len1, len2)):
        diff = array1[idx] - array2[idx]
        diff_to_c[diff].append(idx)
    
    # 匹配所有合法index_b
    target_b_val = array2[index_a] - array1[index_a]
    b_candidates = val_to_b.get(target_b_val, [])
    if not b_candidates:
        return []
    
    # 匹配每个b对应的合法c
    valid_pairs = []
    for idx_b in b_candidates:
        # index_b需要是array2的合法索引
        if idx_b >= len2:
            continue
        target_c = array2[idx_b]
        c_candidates = diff_to_c.get(target_c, [])
        for idx_c in c_candidates:
            valid_pairs.append( (idx_b, idx_c) )
    return valid_pairs

复杂度对比 #

• 暴力双重遍历的时间复杂度为O(n²)，数组长度超过1e4时就会出现明显的性能问题
• 上述哈希查表方案整体时间复杂度为O(n)，预处理只需要遍历两次数组，后续查询都是常数级，哪怕数组长度到百万级也可以快速返回结果。

内容的提问来源于stack exchange，提问作者D. Brown