题目解析

题目的意思是给一个数组，找到里面最长的等差数列（子序列， 不要求紧邻）。

解答

既然是等差数列，那么首先要找到的是差值d，这个差值需要两个数的差值，那么用两个for来遍历所有可能的d，然后再使用这个d来找到之后的数（也就是再用一个for），因为这样时间复杂度比较高，故使用unordered_set来保存所有数，之后的数可以直接查询到
时间复杂度O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int longestArithSeqLength(vector<int>& A) {
        unordered_set<int> a;
        int result = 0;
        for (int i = 0; i < A.size(); i++) {
            a.insert(A[i]);    
        }
        for (int i = 0; i < A.size()-1; i++) {
            for (int j = i+1; j < A.size(); j++) {
                int d = A[j] - A[i];

                result = max(result, 2);
                int temp = A[j] + d;
                if (a.count(temp) == 0) continue;
                int temp_count = 2;

                for (int k = j+1; k < A.size(); k++) {
                    if (A[k] == temp) {
                        temp_count++;
                        temp += d;
                    }
                }
                result = max(temp_count, result);
            }    
        }
        return result;
    }
};