Indexes of Subarray Sum

• Đề bài: https://www.geeksforgeeks.org/problems/subarray-with-given-sum-1587115621/1?page=1&sortBy=submissions
• Yêu cầu: Tìm mảng con đầu tiên có độ dài = target

Example
Input: arr[] = [1, 2, 3, 7, 5], target = 12
Output: [2, 4]

• Kỹ thuật: Sliding Window
• Ý tưởng:

• Code

class Solution {
  public:
    vector<int> subarraySum(vector<int> &arr, int target) {
        int currentSum = 0;
        int left = 0; // Chỉ số bắt đầu của cửa sổ
        
        // Vòng lặp chính để mở rộng cửa sổ
        for (int right = 0; right < arr.size(); right++) {
            currentSum += arr[right]; // Thêm phần tử vào tổng hiện tại
            
            // Vòng lặp while để thu hẹp cửa sổ khi tổng vượt quá target
            while (currentSum > target) {
                currentSum -= arr[left]; // Loại bỏ phần tử ở đầu cửa sổ
                left++;                 // Thu hẹp cửa sổ từ bên trái
            }
            
            // Nếu tổng bằng target, chúng ta đã tìm thấy mảng con
            if (currentSum == target) {
                // Trả về chỉ số 1-based (bắt đầu từ 1)
                return {left + 1, right + 1};
            }
        }
        
        // Nếu không tìm thấy mảng con nào
        return {-1}; 
    }
};