leetcode 659

问题

Given an array nums sorted in ascending order, return true if and only if you can split it into 1 or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.

Example 1:

1
2
3
4
5
6
Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3
3, 4, 5

Example 2:

1
2
3
4
5
6
Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3, 4, 5
3, 4, 5

Example 3:

1
2
Input: [1,2,3,4,4,5]
Output: False

Constraints:

  • 1 <= nums.length <= 10000

分析

思路1：对于输入数组中给定的每一个数字 num 而言，其最好的情况是加入到一个以 num-1 结尾的长度大于等于3的连续子序列中，否则要自己建立一个以num为起始数组的长度大于等于 3 连续子序列。若都不行则返回false，若处理完输入数组中所有的数字依然没有发生冲突则返回true。实现过程中需要使用两个hash表来进行预处理。时间复杂度O(n) 空间复杂度 O(n)。

思路2：对于输入数组中给定的每一个数字 num 而言，我们希望可以知道以 num-1 为结尾的连续子串的情况。prev 表示 num之前的一个数组，p1表示以prev结尾的长度为1的子序列的数量，p2表示以prev结尾的长度为2的子序列的数量，p3表示以prev结尾的长度大于等于3的子序列的数量。在处理当前数字 num 时，我们还需要记录num的数量count。如果 prev != num - 1，那么说明 num 单独成为一个子序列的起始，以prev结尾的子序列不应该存在长度等于1或者长度等于2的情况。如果 prev == num-1，那么num的数量应该至少大于等于 p1+p2，否则下一个处理的数字将会大于 prev+1，以prev结尾且子序列长度小于3的子序列将会永远存在。另外在 count >= p1 + p2 的情况下，num应该优先补充以prev结尾且长度为1的子序列（若存在），然后补充以prev结尾长度为2的子序列（若存在），其次补充以prev结尾长度大于等于3的子序列。处理完之后更新 prev 为num，同时更新p1，p2，p3 为相应的值。时间复杂度O(n)，空间复杂度O(1)。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> need, freq;
        for (int a: nums) freq[a]++;
        for (int a: nums) {
            if (freq[a] == 0)
                continue;
            freq[a]--;
            if (need[a] != 0) {
                need[a+1]++;
                need[a]--;
            } else if (freq[a+1] > 0 && freq[a+2] > 0) {
                freq[a+1]--;
                freq[a+2]--;
                need[a+3]++;
            } else {
                return false;
            }
        }
        return true;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool isPossible(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        int prev = nums[0], p1 = 0, p2 = 0, p3 = 0;
        while (i < n) {
            int a = nums[i];
            int count = 0;
            while (i < n && a == nums[i]) {
                ++i;
                ++count;
            }
            int c1, c2, c3;
            if (prev != a-1) {
                if (p1 != 0 || p2 != 0)
                    return false;
                c1 = count, c2 = 0, c3 = 0;
            } else {
                if (count < p1+p2)
                    return false;
                c2 = p1;
                c3 = p2 + min(count-p1-p2, p3);
                c1 = max(0, count-p1-p2-p3);
            }
            prev = a;
            p1 = c1, p2 = c2, p3 = c3;
        }
        return p1==0 && p2==0;
    }
};