[小米OJ] 4. 最长连续数列

思路：

时间限制为O(n)，即不能使用先排序后寻找的方法。

这里利用哈希表查询插入复杂度都为O(1)的特性来解，利用一个哈希表来保存每一个数字以及其所在数列的长度。

遍历每一个数字n：查询表中是否存在n-1和n+1，若存在，则hash[n]的值为1 + hash[n-1] + hash[n+1]，若不存在即是 1.

同时，为了预防相同数字多次判断，每一次遍历时判断该数字在表中的value是否为0，若不为0说明已经判断过了，跳过即可。

#include <bits/stdc++.h>

using namespace std;

int main()

{

    string input;

    while (cin >> input)

    {

        istringstream iss(input);

        string temp;

        vector<int> vec;

        map<int, int> mapping;

        int maxNum = -;

        while (getline(iss, temp, ','))

        {

            vec.push_back(atoi(temp.c_str()));

            mapping[atoi(temp.c_str())] = ;

        }

        for (auto c : vec)

        {

            if (mapping[c] == )

            {

                mapping[c] = ;

                if (mapping.count(c - ))

                {

                    mapping[c] += mapping[c - ];

                }

                if (mapping.count(c + ))

                {

                    mapping[c] += mapping[c + ];

                }

                maxNum = maxNum > mapping[c] ? maxNum : mapping[c];

            }

        }

        cout << maxNum << endl;

    }

    return ;

}