如何在整数列表中找到两整数重复次数相同的最长子序列？

核心思路是通过跟踪两个目标数的计数差，结合哈希表记录差值首次出现的索引，快速定位满足条件的最长子数组：

• 维护两个计数器，分别统计目标数i1和i2的出现次数。
• 用哈希表存储计数差值（i1计数 - i2计数）与首次出现该差值的索引的映射，初始时存入{0: -1}（代表未遍历任何元素时，计数差为0，对应虚拟索引-1）。
• 遍历数组时，更新计数器并计算当前差值：
  • 若差值已在哈希表中，说明从哈希表记录的索引的下一位到当前索引的子数组中，i1和i2的出现次数相同，计算该子数组长度并更新最大值。
  • 若差值未在哈希表中，将其与当前索引存入哈希表。

代码实现 #

def longest_equal_subsequence(nums, i1, i2):
    count_i1 = 0
    count_i2 = 0
    diff_map = {0: -1}
    max_len = 0
    for idx, num in enumerate(nums):
        if num == i1:
            count_i1 += 1
        elif num == i2:
            count_i2 += 1
        diff = count_i1 - count_i2
        if diff in diff_map:
            current_len = idx - diff_map[diff]
            if current_len > max_len:
                max_len = current_len
        else:
            diff_map[diff] = idx
    return max_len

示例验证 #

用你提供的测试用例验证：

nums = [9, 5, 7, 33, 9, 5, 5, 5, 8, 5, 33, 33, 6, 15, 8, 5, 6]
print(longest_equal_subsequence(nums, 33, 5))  # 输出9

当遍历到最后一个元素（索引16）时，i1累计出现3次，i2累计出现6次，差值为-3。哈希表中-3对应的索引是7，因此子数组长度为16 - 7 = 9，正好对应示例中满足条件的最长子数组。

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