c++等差子序列問題怎么解決

# C++等差子序列問題怎么解決

## 問題定義

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

## 解法思路

### 方法一：暴力枚舉（時間復雜度O(n3)）

```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(n2)）

使用二維數組 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(n2)）

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時，應考慮更高級的算法或剪枝策略

擴展思考

該問題可以延伸為尋找最長等差子序列或統計等差子序列數量，核心思路仍然基于動態規劃，但需要調整狀態轉移方程。 “`