ขนาด Subarray น้อยที่สุดที่ผลรวม ≥ S (Minimum Size Subarray Sum) ใน C++

ขนาด Subarray น้อยที่สุดที่ผลรวม ≥ S (Minimum Size Subarray Sum)

ให้อาร์เรย์ n องค์ประกอบ และจำนวนเต็มบวก s หาความยาวน้อยที่สุดของ subarray ติดต่อกันที่ผลรวม ≥ s ถ้าไม่มีคืนค่า 0

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

ขั้นตอนการแก้ปัญหา (Sliding Window / Two Pointers)

1. ans = 0 (หรือ INT_MAX), j = 0, sum = 0
2. วน i = 0 ถึง n-1:
   • sum += A[i]
   • ในขณะที่ sum - A[j] >= s: sum -= A[j++] (หดหน้าต่างจากซ้าย)
   • ถ้า sum >= s: ans = min(ans, i - j + 1)
3. คืนค่า ans (ถ้าเป็น INT_MAX คืน 0)

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

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

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(), ans = INT_MAX, j = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            while (sum - nums[j] >= target) sum -= nums[j++];
            if (sum >= target) ans = min(ans, i - j + 1);
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

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

Output: 2