leetcode 最长定差子序列 -- Map

给你一个整数数组 arr 和一个整数 difference，请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列，并返回其中最长的等差子序列的长度。

示例1

输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例2

输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例3

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

提示：

• 1 <= arr.length <= 10^5
• -10^4 <= arr[i], difference <= 10^4

该题需要注意的地方为：

• 要按照数组本来的顺序，不能对数组进行排序操作

在解题时，我自己的想法是外面一个循环，里面再从当前元素出发，寻找当前元素的等差数列，虽然有对使用过的元素进行标记，不再循环，但是依然是将近O(n*n)的复杂度。我朋友的想法就是使用Map数组来存储每个元素的等差数列长度，只需要一层循环，在循环时，查找Map数组中是否有当前元素的前一项，如果有，取出前一项的等差数列的长度，将这个长度加1就是当前元素的等差数列的长度。最后只需要找出Map数组中等差数列长度的最大值了。由于Map数组查找的算法复杂度为O(logn)，因此总体的算法复杂度为O(nlogn)。

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        map<int,int> storeMap;
        for(int i=0;i<arr.size();i++){
            int preValue = arr[i] - difference;
            auto iter = storeMap.find(preValue);
            if(iter != storeMap.end()){
                auto iter2 = storeMap.find(arr[i]);
                if(iter2 != storeMap.end()){
                    iter2->second = iter->second+1;
                }
                else{
                    storeMap.insert(pair<int,int>(arr[i], iter->second + 1));
                }
            }
            else{
                storeMap.insert(pair<int,int>(arr[i], 1));
            }
        }
        int max_len = 1;
        for(auto iter=storeMap.begin();iter!=storeMap.end();iter++){
            if(iter->second > max_len){
                max_len = iter->second;
            }
        }
        return max_len; 
    }
};

题目链接：https://leetcode.com/contest/weekly-contest-157/problems/longest-arithmetic-subsequence-of-given-difference/