[LeetCode]Longest Harmonious Subsequence

我们用一个map维护由单一数字组成的子序列的长度，即子序列又单一一个数字构成。我们遍历原数组的时候，当我们遍历到nums[i]，只需要每次去找相邻两个元素(nums[i] + 1, nums[i] - 1)在map里的长度，取较长的与当前数字子序列的长度相加就是在当前位置结尾的最长LHS。我们每一次不断更新LHS，linear time，constant space（0-9只有十个数）。代码如下：

	class Solution {
	public:
	int findLHS(vector<int>& nums) {
	int len = nums.size(), res = 0;
	unordered_map<int, int> map;
	for(int i = 0; i < len; ++i)
	{
	++map[nums[i]];
	int adj = max(map[nums[i] - 1], map[nums[i] + 1]);
	res = max(res, adj? adj + map[nums[i]]: 0);
	}
	return res;
	}
	};

view raw Longest Harmonious Subsequence.cpp hosted with ❤ by GitHub