Cho một mảng các số nguyên nums và một số nguyên k. Hãy tìm tổng số lượng mảng con liên tiếp có tổng các phần tử đúng bằng k.
Ví dụ 1:
Input: nums = [1, 1, 1], k = 2
Output: 2
Giải thích: Có 2 mảng con: [1, 1] ở đầu và [1, 1] ở cuối.Ví dụ 2:
Input: nums = [1, 2, 3], k = 3
Output: 2
Giải thích: [1, 2] và [3].Định Dạng Đầu Vào (Input)
Dòng 1: Mảng số nguyên nums
Dòng 2: Số nguyên k
Dòng 2: Số nguyên k
Định Dạng Đầu Ra (Output)
Một số nguyên duy nhất là số mảng con thỏa mãn
Ràng Buộc (Constraints)
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[1, 1, 1]
2
Output:
2
Giải thích: 2 mảng con
Ví dụ 2:
Input:
[1, 2, 3]
3
Output:
2
Giải thích: [1,2] và [3]
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Kỹ thuật Tổng Tiền Tố (Prefix Sum) & Hash Map O(n)
Tổng của mảng con từ i đến j bằng prefixSum[j] - prefixSum[i-1].
Điều kiện tổng bằng k tương đương với: prefixSum[j] - prefixSum[i-1] == k hay prefixSum[i-1] == prefixSum[j] - k.
Dùng Hash Map lưu tần suất xuất hiện của các giá trị prefixSum đã gặp.
Dữ liệu đầu vào (Input):
[1, 1, 1]
2
Kết quả kỳ vọng (Expected Output):
2
Dữ liệu đầu vào (Input):
[1, 2, 3]
3
Kết quả kỳ vọng (Expected Output):
2
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
