โปรแกรมลบ sublist เพื่อให้จำนวนน้อยกว่าและมากกว่า k เท่ากันใน C++

ภาพรวมปัญหา

ให้อาร์เรย์ nums และจำนวน k สามารถลบ sublist (ช่วงติดต่อกัน) ได้สูงสุด 1 ครั้ง ต้องการความยาวสูงสุดของอาร์เรย์ที่เหลือ ที่ทำให้จำนวนน้อยกว่า k เท่ากับจำนวนมากกว่า k

ตัวอย่าง

Input: nums = [6, 10, 8, 9, 3, 5], k = 6

Output: 5

คำอธิบาย: ลบ [9] ได้ [6,10,8,3,5] → น้อยกว่า 6: {3,5} (2 ตัว), มากกว่า 6: {10,8} (2 ตัว)

แนวทางแก้ปัญหา (Prefix Sum + Hash Map)

แปลงปัญหา: ให้ค่าใหม่แทนตัวเลข

• num < k → +1
• num > k → -1
• num == k → 0 (ไม่ส่งผลต่อความต่าง)

ต้องการหา subarray ที่ลบออก (หรือว่า subarray ที่เก็บไว้) ให้ผลรวม = 0

ใช้ Prefix Sum: prefix[i] = ผลรวมค่าใหม่ของ nums[0..i-1]

ต้องการ prefix[j] - prefix[i] = 0 → prefix[j] = prefix[i]

เพื่อให้ความยาวที่เหลือมากที่สุด → subarray ที่ลบสั้นที่สุด → |j-i| น้อยที่สุด

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

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

class Solution {
public:
    int solve(vector& nums, int k) {
        int n = nums.size();
        vector prefix(n + 1, 0);
        
        // Build prefix sum with transformed values
        for (int i = 0; i < n; i++) {
            if (nums[i] < k) prefix[i+1] = prefix[i] + 1;
            else if (nums[i] > k) prefix[i+1] = prefix[i] - 1;
            else prefix[i+1] = prefix[i];
        }
        
        // If total balance is 0, no need to remove
        if (prefix[n] == 0) return n;
        
        // Find shortest subarray with sum = prefix[n] (delta)
        unordered_map firstOccurrence;
        firstOccurrence[0] = 0;
        int minLen = INT_MAX;
        int delta = prefix[n];
        
        for (int i = 1; i <= n; i++) {
            int target = prefix[i] - delta;
            if (firstOccurrence.count(target)) {
                minLen = min(minLen, i - firstOccurrence[target]);
            }
            if (!firstOccurrence.count(prefix[i])) {
                firstOccurrence[prefix[i]] = i;
            }
        }
        
        if (minLen == INT_MAX) return 0;
        return n - minLen;
    }
};

int main() {
    Solution ob;
    vector v = {6, 10, 8, 9, 3, 5};
    int k = 6;
    cout << ob.solve(v, k);
    return 0;
}

ผลลัพธ์

5

ความซับซ้อน

• เวลา: O(N)
• พื้นที่: O(N)

ข้อสังเกต

โค้ดต้นฉบับใช้ map (O(log N) ต่อ operation) สามารถเปลี่ยนเป็น unordered_map ได้ O(1) average

ตรรกะ: ต้องการลบ subarray ที่มีผลรวม = delta (ความต่างรวมของอาร์เรย์ทั้งหมด) ให้สั้นที่สุด