1. Câu hỏi

Cho một mảng số nguyên nums và một số nguyên k, hãy tìm mảng con không trống ngắn nhất trong nums có tổng ít nhất là k và trả về độ dài của mảng con. Nếu không tồn tại mảng con như vậy, hãy trả về -1 . Mảng con là phần liền kề của mảng.

Ví dụ 1:
Đầu vào: nums = [1], k = 1
Đầu ra: 1

Ví dụ 2:
Đầu vào: nums = [1,2], k = 4
Đầu ra: -1

Ví dụ 3:
Đầu vào: nums = [2,-1,2], k = 3
Đầu ra: 3

gợi ý:
1 <= số.độ dài <= 105
-105 <= số[i] <= 105
1 <= k <= 109

Nguồn: LeetCode
Liên kết: https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k

2. Ý tưởng

(1) Tổng tiền tố
Ý tưởng thông thường là sử dụngTiền tố và mảng, nghĩa là preSum[i] lưu tổng tiền tố của nums[0...i - 1], sau đó sử dụng vòng lặp for hai lớp để duyệt tất cả các mảng con và xác định xem tổng các phần tử của nó có lớn hơn không hơn hoặc bằng k. Nếu các điều kiện được đáp ứng, hãy sử dụng biến res ghi lại độ dài tối thiểu của mảng con trong quá trình truyền tải, nếu không thì quá trình truyền tải vẫn tiếp tục. Nếu vẫn không tìm thấy sau khi quá trình truyền tải hoàn tất, -1 sẽ được trả về.Nhưng khi gửi trên LeetCode, thông báo "vượt quá thời gian" sẽ xuất hiện! Điều này cho thấy phương pháp này (độ phức tạp về thời gian là O(n2)) vẫn cần được tối ưu hóa. Để biết các phương pháp tối ưu hóa cụ thể, hãy xem Ý tưởng 2.

(2) Tiền tố và & hàng đợi hai đầu
Tham khảo ý tưởngGiải pháp chính thức cho câu hỏi này.

3. Triển khai mã (Java)

//Ý tưởng 1——Tiền tố và giải pháp lớp { public int shortSubarray(int[] nums, int k) { int res = Integer.MAX_VALUE; int length = nums.length; preSum = new int[length + 1] ; for (int i = 1; i < length + 1; i++) { preSum[i] = preSum[i - 1] + nums[i - 1]; //Nếu một phần tử lớn hơn hoặc bằng k thì độ dài của mảng con ngắn nhất thỏa mãn điều kiện phải là 1 if (nums[i - 1] >= k) { return 1; int i = 0; i < length + 1; i++) { for (int j = i + 1; j < length + 1; j++) { // preSum[j] - preSum[i] là mảng con liên tục [i, Tổng của j) if (preSum[j] - preSum[i] >= k) { res = Math.min(res, j - i); /* Do tính tổng của các mảng con nums[i...j - 1] đã lớn hơn hoặc bằng k và trong vòng lặp for cấp hai, giá trị của i là cố định. Không cần phải mở rộng j để xác định tổng của các mảng con bắt đầu bằng nums[i], vì vậy. bạn có thể trực tiếp thoát khỏi vòng lặp cấp hai hiện tại tại đây. Tuy nhiên, vấn đề vẫn chưa thể giải quyết được về cơ bản khi gửi trên LeetCode sẽ xuất hiện thông báo "vượt quá thời hạn"! */ break; } } } //Nếu không có mảng nào đáp ứng điều kiện, return -1 return res == Integer.MAX_VALUE ? -1 : res } }

//Ý tưởng 2——Tổng tiền tố & lớp hàng đợi hai đầu Giải pháp { public int shortSubarray(int[] nums, int k) { int res = Integer.MAX_VALUE; int length = nums.length long[] preSum = new long; [độ dài + 1]; for (int i = 1; i < length + 1; i++) { preSum[i] = preSum[i - 1] + (long)nums[i - 1]; if (nums[i - 1] >= k) { return 1; } } //Xác định hàng đợi hai đầu Deque deque = new ArrayDeque<>(); int i = 0; i < preSum.length; i++) { while (!deque.isEmpty() && preSum[i] <= preSum[deque.getLast()]) { deque.removeLast(); } while (!deque.isEmpty() && preSum[i] - preSum[deque.peek()] >= k) { res = Math.min(res, i - deque.poll()) ; } deque.add(i); } trả về res == Integer.MAX_VALUE ?