LCS_128..md

description

self_solution

unsolved

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, pair<int, int>> helpMap;
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            if(helpMap.count(nums[i]) == 0) {
                int left = 0;
                int right = 0;
                if(helpMap.count(nums[i] + 1) && helpMap.count(nums[i] - 1)) {
                    left = helpMap[nums[i] - 1].first;
                    right = helpMap[nums[i] + 1].second;
                    helpMap[nums[i] - 1] = make_pair(left, right);
                    helpMap[nums[i]] = make_pair(left, right);
                    helpMap[nums[i] + 1] = make_pair(left, right);
                } else if(helpMap.count(nums[i] + 1)) {
                    right = helpMap[nums[i] + 1].second;
                    left = min(nums[i], helpMap[nums[i] + 1].first);
                    helpMap[nums[i]] = make_pair(left, right);
                    helpMap[nums[i] + 1] = make_pair(left, right);
                } else if(helpMap.count(nums[i] - 1)) {
                    left = helpMap[nums[i] - 1].first;
                    right = max(nums[i], helpMap[nums[i] - 1].second);
                    helpMap[nums[i]] = make_pair(left, right);
                    helpMap[nums[i] - 1] = make_pair(left, right);
                } else {
                    left = nums[i];
                    right = nums[i];
                    helpMap[nums[i]] = make_pair(left, right);
                }
            }
        }

        int maxLen = 0;
        for(auto  it = helpMap.begin(); it != helpMap.end(); it++) {
            maxLen = max(maxLen, it->second.second - it->second.first + 1);
        }
        return maxLen;
    }
};

[0,3,7,2,5,8,4,6,0,1] 用例不过。helpMap中储存当前某个元素关联到的最左，最右的两个边界。 但是实际上，前面的元素保存一个较小的连续边界，不会被后面新的边界更新。

官方哈希

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> helpSet;
        for(auto num : nums) {
            helpSet.insert(num);
        }

        int maxLen = 0;
        for(auto num : nums) {
            int len = 1;
            int currentNum = num;
            if(!helpSet.count(num - 1)) { // nice!!!
                while(helpSet.count(num + 1)) {
                    num++;
                    len++;
                }
                maxLen = max(maxLen, len);
            }
        }
        return maxLen;
    }
};

1. 首先使用hashSet将所有的数据保存下来，便于O(1)找到某一个元素。这里不需要键值对，又能排重，所以选择unordered_set
2. 遍历原来的数组，尝试以num为底，找数组中大于其的数，持续遍历 找到长度
3. 实际查询的时候，要求这个num必须在helpSet中没有 小于它1 的数据。这样就O(1)的避免了大量的重复查询。
4. 如果没有比它小1的数据，以其为底开始1步长的向后查找序列。 [100,4,200,1,3,2] 实际上 100 200 1 只进行了三次内循环 time : O(n) space : O(n)

other_哈希

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> helpMap;
        int maxLen = 0;
        for(auto num : nums) {
            if(!helpMap.count(num)) {
                int left = 0;
                int right = 0;
                if(helpMap.count(num + 1)) {
                    right = helpMap[num + 1];
                }
                if(helpMap.count(num - 1)) {
                    left = helpMap[num - 1];
                }
                int len = left + right + 1;
                helpMap[num] = len;
                helpMap[num + right] = len;
                helpMap[num - left] = len;
                maxLen = max(maxLen, len);
            }
        }
        return maxLen;
    }
};

哈希表中存储当前的num值，以及这个num所在的连续序列的长度。(不一定靠谱，每一次更新前的左右端点对应的长度是准的)

1. 遍历nums数组，当当前num此前没有处理过的时候，开始进行处理
2. 如果num + 1在哈希表中，说明存在大于当前元素1的序列。
3. 如果num - 1在哈希表中，说明存在小于当前元素1的序列。
4. 获取左右两个序列的长度 left + right
5. 将三部分长度统一起来，获取最新的长度 left + right + 1
6. 使用该长度，更新help[num] help[num-left] help[num+right] 将整个更新序列的最左右两端的值更新
7. 至于num -1 num + 1，现在已经是在序列内部了，之后也不会再出现num来使用num-1 和num+1、

举例：[100,4,200,1,3,2]

1. 100 进入 没有左右两端，更新help[100]=1
2. 4 进入，没有左右两端，更新help[4]=1
3. 200进入，没有左右两端，更新help[200]=1
4. 1进入，没有左右两端，更新help[1]=1
5. 3进入，有右端，获取新的长度为2，更新help[3] = 2 help[3+1]=2
6. 2进入，有左右两端，获取新的长度为 1 + 2 +1 =4，help[2] = 4 help[2-1] =4 help[2+2] =4