904. Fruit Into Baskets

In a row of trees, the i-th tree produces fruit with type tree[i].

You start at any tree of your choice, then repeatedly perform the following steps:

1. Add one piece of fruit from this tree to your baskets. If you cannot, stop.

2. Move to the next tree to the right of the current tree. If there is no tree to the right, stop.

Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.

You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.

What is the total amount of fruit you can collect with this procedure?

Example 1:

Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].

Example 2:

Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].

Example 3:

Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].

Example 4:

Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.

Note:

1. 1 <= tree.length <= 40000

2. 0 <= tree[i] < tree.length

要求longest subarray with only 2 distinct numbers，可以利用sliding window用two pointers紀錄start和end位置，還有hashmap來記錄number出現次數來計算。

// Sliding Window
int totalFruit(vector<int>& tree) { // time: O(n); space: O(1)
    unordered_map<int, int> m;
    int res = 0, i = 0; // i is start, j is end
    for (int j = 0; j < tree.size(); ++j) {
        ++m[tree[j]];
        while (m.size() > 2) {
            --m[tree[i]];
            if (m[tree[i]] == 0) m.erase(tree[i]);
            ++i;
        }
        res = max(res, j - i + 1);
    }
    return res;
}

優化空間使用，分成3種cases來考慮。res代表global result，cur代表local result，count_second代表第二種水果連續出現的數量。

1. 當前的水果等於第二種水果:

   local result + 1 第二種水果的連續數量+1

2. 當前的水果等於第一種水果: local result + 1 此時原本的第二種水果不是連續出現了，要把原本第二種水果當成新的第一種水果，然後新的第二種水果為當前遇到的水果，在這case下就是原本的第一種水果。 要重設第二種水果連續出現次數為1

3. 當前的水果不等於已經看得到兩種水果: 原本的第二種水果並非連續出現了，重新設定新的第一種水果為原本第二種水果，捨棄原本第一種水果，然後把新的第二種水果設為當前遇到的水果。 local result 設為原先第二種水果連續出現次數+1 重設第二種水果連續出現次數為1

int totalFruit(vector<int>& tree) { // time: O(n); space: O(1)
    int res = 0, cur = 0, first = 0, second = 0, count_second = 0;
    for (int fruit : tree) {
        if (fruit == second) {
            cur += 1;
            count_second += 1;
        } else if (fruit == first) {
            cur += 1;
            count_second = 1;
            first = second;
            second = fruit;
        } else {
            cur = count_second + 1;
            count_second = 1;
            first = second;
            second = fruit;
        }
        res = max(res, cur);
    }
    return res;
}