描述

这是一篇针对初学者的题解。共用两种方法解决。
知识点：数组，set，排序
难度：一星

题解

题目抽象：给定一个长度为5（排除空vector），包含0-13的数组，判断公差是否为1.

方法一：set+遍历

我们分两种情况考虑，
一. 如果vector中不包含0的情况：
那么如何判断呢？因为需要是顺子，所以首先不能有重复值， 如果没有重复值，那么形如[1 2 3 4 5]
[5 6 7 8 9]， 会发现最大值与最小值的差值应该小于5.

二. 如果vector中包含0：
发现除去0后的值，判断方法和1中是一样的。

所以根据如上两个条件，算法过程如下：

1. 初始化一个set，最大值max_ = 0, 最小值min_ = 14
2. 遍历数组， 对于大于0的整数，没有在set中出现，则加入到set中，同时更新max_, min_
3. 如果出现在了set中，直接返回false
4. 数组遍历完，最后再判断一下最大值与最小值的差值是否小于5

代码如下：

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if (numbers.empty()) return false;
        set<int> st;
        int max_ = 0, min_ = 14;
        for (int val : numbers) {
            if (val > 0) {
                if (st.count(val) > 0) return false;
                st.insert(val);
                max_ = max(max_, val);
                min_ = min(min_, val);
            }
        }
        return max_ - min_ < 5;
    }
};

时间复杂度：O(N)
空间复杂度：O(N)

方法二：排序+遍历

根据方法一的分析，实现上如果不用set判断是否有重复值的话，还可以先排序，然后如果有重复值，那么肯定相邻。
所以代码如下：

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if (numbers.empty()) return false;
        sort(numbers.begin(), numbers.end());
        int i = 0, sz = numbers.size();
        for (int j=0; j<sz; ++j) {
            if (numbers[j] == 0) {
                ++i; // i 记录最小值的下标
                continue;
            }
            if (j+1<sz && numbers[j] == numbers[j+1]) return false;
        }
        return numbers.back() - numbers[i] < 5;
    }
};

时间复杂度：O(NlogN)
空间复杂度：O(1)