1027.cpp (1006B)
1 class Solution { 2 public: 3 int longestArithSeqLength(vector<int> &nums) { 4 unordered_map<int, vector<int>> um; 5 int res = 2; 6 7 for (int i = 0; i < nums.size(); i++) 8 um[nums[i]].push_back(i); 9 for (const auto &[num1, vec1] : um) { 10 res = max(res, (int)vec1.size()); 11 for (const auto &[num2, vec2] : um) { 12 if (num1 == num2) continue; 13 14 auto it = lower_bound(vec2.begin(), vec2.end(), vec1.front() + 1); 15 if (it == vec2.end()) continue; 16 17 int diff = num2 - num1, crnt = *it, count = 2, next; 18 while (true) { 19 if (!um.count(next = nums[crnt] + diff)) break; 20 auto it = lower_bound(um[next].begin(), um[next].end(), crnt + 1); 21 if (it == um[next].end()) break; 22 crnt = *it, count++; 23 } 24 res = max(res, count); 25 } 26 } 27 return res; 28 } 29 };