c++等差子序列问题怎么解决

# C++等差子序列问题怎么解决

## 问题定义

等差子序列是指一个序列中至少包含3个元素，且相邻元素差值相等的子序列。例如在序列 `[1, 3, 5, 7]` 中，`[1, 3, 5]` 和 `[3, 5, 7]` 都是等差子序列。

## 解法思路

### 方法一：暴力枚举（时间复杂度O(n³)）

```cpp
bool hasArithmeticSubsequence(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = nums[j] - nums[i];
            for (int k = j + 1; k < n; k++) {
                if (nums[k] - nums[j] == diff) {
                    return true;
                }
            }
        }
    }
    return false;
}

方法二：动态规划（时间复杂度O(n²)）

使用二维数组 dp[i][d] 表示以第i个元素结尾，公差为d的等差子序列长度：

bool hasArithmeticSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<unordered_map<int, int>> dp(n);
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            long diff = (long)nums[i] - nums[j];
            if (diff < INT_MIN || diff > INT_MAX) continue;
            
            int cnt = dp[j].count(diff) ? dp[j][diff] : 1;
            if (cnt + 1 >= 3) return true;
            dp[i][diff] = cnt + 1;
        }
    }
    return false;
}

方法三：哈希表优化（时间复杂度O(n²)）

bool hasArithmeticSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<unordered_map<int, bool>> memo(n);
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int diff = nums[i] - nums[j];
            if (memo[j].count(diff)) {
                return true;
            }
            memo[i][diff] = true;
        }
    }
    return false;
}

性能对比

实际应用建议

1. 对于算法竞赛，推荐动态规划解法
2. 工程场景中若需要多次查询，可使用哈希表优化版
3. 当n>1000时，应考虑更高级的算法或剪枝策略

扩展思考

该问题可以延伸为寻找最长等差子序列或统计等差子序列数量，核心思路仍然基于动态规划，但需要调整状态转移方程。 “`