Fruit Into Baskets ใน C++: หา Subarray ยาวสุดที่มีค่าต่างกัน ≤ 2 ชนิด

โจทย์

อาร์เรย์ tree[i] = ชนิดผลไม้ มีตะกร้า 2 ใบ แต่ละใบเก็บได้ 1 ชนิด เริ่มต้นที่ไหนก็ได้ เดินขวาเรื่อยๆ หาจำนวนผลไม้สูงสุดที่เก็บได้

ตัวอย่าง: [3,3,3,1,2,1,1,2,3,3,4] → 5 (subarray [1,2,1,1,2])

แนวคิด: Sliding Window + Hash Map นับความถี่

รักษา window [j, i] ที่มีชนิดผลไม้ ≤ 2 ชนิด ขยาย i เพิ่มชนิดใหม่ ถ้าเกิน 2 → กด j ลดลงจนเหลือ 2

ขั้นตอน

1. j = 0, ans = 0, map m
2. ลูป i = 0 ถึง n-1:
   • m[tree[i]]++
   • while m.size() > 2 && j <= i:
     • m[tree[j]]--
     • ถ้า m[tree[j]] == 0 → m.erase(tree[j])
     • j++
   • ans = max(ans, i - j + 1)
3. คืน ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int n = tree.size(), j = 0, ans = 0;
        unordered_map<int, int> m;
        for (int i = 0; i < n; i++) {
            m[tree[i]]++;
            while (m.size() > 2 && j <= i) {
                if (--m[tree[j]] == 0) m.erase(tree[j]);
                j++;
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {3,3,3,1,2,1,1,2,3,3,4};
    cout << ob.totalFruit(v); // 5
    return 0;
}

อินพุต / เอาต์พุต

Input: [3,3,3,1,2,1,1,2,3,3,4]

Output: 5

ความซับซ้อน

• Time: O(n) - i, j เดินไปข้างหน้าจบ
• Space: O(1) - map เก็บสูงสุด 3 keys