Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
in.txt
solve.cpp

README.md

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Solution

刚开始以为是DP,没有思路!

看了答案发现其实并不是很复杂,关键找对思路。。

使用map,key为数值,value为长度, 设当前遍历数组的值为i

  • 若i已经在map中,忽略。
  • 否则left = map[i - 1] or 0, right = map[i + 1] or 0,则map[i] = left + right + 1,即当前值的长度等于它左相邻和右相邻长度之和+1.
  • 同时需要更新边界值,即map[i - left] = map[i], map[i + right] = map[i], 因为我们第一步忽略了已经存在的值,因此我们只需要维护边界值即可,而不用把中间的值同时更新.
  • 返回最大的map值即可
int longestConsecutive(vector<int> &nums) {
	unordered_map<int, int> map;
	int res = 0;
	for (int i : nums) {
		if (map.find(i) != map.end()) {
			continue;
		}
		int left = getOrElse(map, i - 1);
		int right = getOrElse(map, i + 1);
		int sum = left + right + 1;
		res = max(res, sum);
		map[i] = sum;
		map[i - left] = sum;
		map[i + right] = sum;
	}
	return res;
}
You can’t perform that action at this time.