LeetCode: Longest Consecutive Sequence

想到map了，可惜没想到用erase来节省空间，看了网上答案

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        map<int, int> rec;
        for (int i = 0; i < num.size(); i++) rec.insert(pair<int, int>(num[i], 1));
        int maxcon = 0;
        for (int i = 0; i < num.size(); i++) {
            map<int, int>::iterator it = rec.find(num[i]);
            if (it != rec.end()) {
                int left = num[i]-1;
                int right = num[i]+1;
                while (1) {
                    map<int, int>::iterator iter = rec.find(left);
                    if (iter != rec.end()) {
                        left--;
                        rec.erase(iter);
                    }
                    else break;
                }
                left++;
                while (1) {
                    map<int, int>::iterator iter = rec.find(right);
                    if (iter != rec. end()) {
                        right++;
                        rec.erase(iter);
                    }
                    else break;
                }
                right--;
                maxcon = max(maxcon, right - left + 1);
                rec.erase(it);
            }
        }
        return maxcon;
    }
};

贴上自己写的更加简单的代码

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        map<int, int> S;
        int sum = 0;
        for (int i = 0; i < num.size(); i++) S[num[i]] = 1;
        for (int i = 0; i < num.size(); i++) {
            if (S.count(num[i])) {
                int left = 1;
                int tmp = num[i];
                while (S.count(tmp-left)) {
                    S.erase(tmp-left);
                    left++;
                }
                int right = 1;
                while (S.count(tmp+right)) {
                    S.erase(tmp+right);
                    right++;
                }
                S.erase(tmp);
                sum = max(sum, left+right-1);
            }
        }
        return sum;
    }
};

C#

public class Solution {
    public int LongestConsecutive(int[] nums) {
        Dictionary<int, int> S = new Dictionary<int, int>();
        int ans = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (!S.ContainsKey(nums[i])) S.Add(nums[i], 1);
        }
        for (int i = 0; i < nums.Length; i++) {
            if (S.ContainsKey(nums[i])) {
                int left = 1;
                int tmp = nums[i];
                while (S.ContainsKey(tmp - left)) {
                    S.Remove(tmp - left);
                    left++;
                }
                int right = 1;
                while (S.ContainsKey(tmp + right)) {
                    S.Remove(tmp + right);
                    right++;
                }
                S.Remove(tmp);
                ans = Math.Max(ans, left + right - 1);
            }
        }
        return ans;
    }
}