如何判断升序整数数组中是否存在长度>3、公差为x的等差数列

给定一个升序的随机整数数组，需判断数组中是否存在长度大于3、公差为x的等差数列。

示例：

• 输入：数组=[1,2,4,5,8,10,17,19,20,23,30,36,40,50]，x=10
• 输出：True

示例说明：数组中包含[10,20,30,40,50]，这是一个长度为5、公差为10的等差数列。

自己编写的Python代码如下，但返回结果为9而非预期的4，需要解决同一序列重复计数和排除无关序列计数的问题：

df = [1,10,11,20,21,30,40]
i=0
common_differene=10
df_len=len(df)
for position_1 in range(df_len):
    for position_2 in range(df_len):
        if df[position_1] + common_differene == df[position_2]:
            position_1=position_2
            i=i+1
print(i)

1. 嵌套循环遍历所有位置对，会重复匹配同一序列的不同起始点（比如[10,20,30,40]会被从10、20、30分别计数），导致重复累加。
2. 修改外层循环变量position_1会打乱循环的正常遍历逻辑，引发更多无效匹配。
3. 仅简单计数两两匹配的次数，无法区分连续的长序列和零散的匹配对。

方法1：哈希集合+跳过已处理元素 #

利用数组升序特性，结合哈希集合快速查找下一个等差项，同时跳过已作为序列后续元素的起始点，避免重复计算：

def has_long_arithmetic_sequence(arr, x):
    num_set = set(arr)
    processed = set()
    for num in arr:
        if num in processed:
            continue
        current = num
        length = 1
        while current + x in num_set:
            length += 1
            current += x
            processed.add(current)
        if length > 3:
            return True
    return False

# 测试
df = [1,10,11,20,21,30,40]
print(has_long_arithmetic_sequence(df, 10))  # 输出True

• 逻辑：将数组转为集合实现O(1)查找；用processed记录已处理的后续元素，避免重复遍历同一序列的不同起始点；一旦找到长度>3的序列直接返回结果。

方法2：动态规划记录序列长度 #

用字典记录以每个元素结尾的、公差为x的等差数列长度，遍历过程中实时判断是否满足条件：

def has_long_arithmetic_sequence_dp(arr, x):
    dp = {}
    for num in arr:
        dp[num] = dp.get(num - x, 0) + 1
        if dp[num] > 3:
            return True
    return False

# 测试
df = [1,10,11,20,21,30,40]
print(has_long_arithmetic_sequence_dp(df, 10))  # 输出True

• 逻辑：对每个元素num，若num-x存在，则当前序列长度为num-x对应的长度+1，否则为1；只要某个元素对应的长度超过3，直接返回True。

修正原代码版本 #

如果要基于原代码逻辑修改，需避免修改循环变量，一次性遍历完整序列并跳过已处理元素：

df = [1,10,11,20,21,30,40]
common_difference = 10
df_len = len(df)
processed = set()
max_length = 0

for position_1 in range(df_len):
    num = df[position_1]
    if num in processed:
        continue
    current_pos = position_1
    current_length = 1
    # 遍历寻找后续等差项
    while True:
        found = False
        # 数组升序，从当前位置后开始找
        for position_2 in range(current_pos + 1, df_len):
            if df[current_pos] + common_difference == df[position_2]:
                current_length += 1
                processed.add(df[position_2])
                current_pos = position_2
                found = True
                break
        if not found:
            break
    if current_length > max_length:
        max_length = current_length

print(max_length)  # 输出4，对应目标序列长度

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