- Đề 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}; }
};