1027. Longest Arithmetic Sequence
问题描述：
Given an arrayAof integers, return thelengthof the longest arithmetic subsequence inA.
Recall that asubsequenceofAis a listA[i_1], A[i_2], ..., A[i_k]with0 <= i_1 < i_2 < ... < i_k <= A.length - 1, and that a sequenceBisarithmeticifB[i+1] - B[i]are all the same value (for0 <= i < B.length - 1).
Example 1:
Input: [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].
Note:
2 <= A.length <= 20000 <= A[i] <= 10000
解题思路：
在数组中寻找最长的等差数列并且返回长度。
对于每一个数字，存在一个以该数字结尾的数列，可能只包含它一个，也可能包含其他的值。
我们对于每一个数值A[i]，遍历之前的值A[j]，看看之前的值有没有差为A[i] - A[j] 等差数列存在
如果有，我们就存入A[i]差为A[i] - A[j]的等差数列的长度为之前的长度加一。
这里我用了两层map嵌套实现
外层：<index, innerMap>
内层：<diff, length>
我从下标为一的值开始向后遍历并且检索前面的，并没有初始化map，所以要对不存在的键值进行处理。
代码：
class Solution { public: int longestArithSeqLength(vector<int>& A) { //we can using a map to store the possible arithmetic sequence. //the key is the index of array //the value is the map of possible difference of arithmetic sequence and the length of its //we can use a variable to record current maximum length //time complexity is O(n^2) if(A.size() < 3) return A.size(); unordered_map<int, unordered_map<int,int> > m; int n = A.size(); int ret = 1; for(int i = 1; i < n; ++i){ for(int j = 0; j < i; ++j){ int diff = A[i]-A[j]; if(m.count(j) != 0 && m[j].count(diff) != 0){ m[i][diff] = m[j][diff]; }else{ m[i][diff] = 1; } m[i][diff]++; ret = max(ret, m[i][diff]); // std::cout << A[i] << " : " << A[j] << std::endl; // std::cout << diff << " : " << ret << std::endl; } } //++ret; return ret; } };优质内容筛选与推荐>>
1、章节十四、3-执行JavaScript命令
2、JavaScript的68个技巧一
3、20172302《程序设计与数据结构》实验三 敏捷开发与XP实践报告
4、loadrunner基础学习笔记六-运行负载
5、修改插件