Đề bài
Cho một mảng nhị phân nums và một số nguyên goal, hãy trả về số lượng dãy con không rỗng có tổng bằng goal.
Một dãy con là một phần liên tục của mảng.
Ví dụ 1:
Đầu vào: nums = [1,0,1,0,1], goal = 2
Đầu ra: 4
Giải thích: Có 4 dãy con với tổng bằng 2:
[1,0,1]
[1,0,1]
[0,1,0,1]
[1,0,1]
Ví dụ 2:
Đầu vào: nums = [0,0,0,0,0], goal = 0
Đầu ra: 15
Ràng buộc:
1 <= nums.length <= 30,000
nums[i] là 0 hoặc 1.
0 <= goal <= nums.length
Cách làm
#include <iostream>
#include <unordered_map>
using namespace std;
int demDayCon(int nums[], int n, int goal) {
unordered_map<int, int> mapTong;
mapTong[0] = 1; // Khoi tao de xet truong hop tong = goal tu dau mang
int tong = 0, ketqua = 0;
for (int i = 0; i < n; i++) {
tong += nums[i];
if (mapTong.find(tong - goal) != mapTong.end()) {
ketqua += mapTong[tong - goal];
}
mapTong[tong]++;
}
return ketqua;
}
int main() {
int nums[] = {1, 0, 1, 0, 1};
int n = sizeof(nums) / sizeof(nums[0]);
int goal = 2;
cout << "So luong day con co tong bang " << goal << " la: " << demDayCon(nums, n, goal) << endl;
return 0;
}
