Giả sử chúng ta có một mảng được gọi là nums và một giá trị khác k. Chúng ta phải tìm số dãy con không rỗng của các số sao cho tổng của phần tử nhỏ nhất và lớn nhất trên nó nhỏ hơn hoặc bằng k. Các câu trả lời có thể rất lớn vì vậy hãy trả lại câu trả lời mod 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là nums =[4,6,7,8] k =11, thì đầu ra sẽ là 4 vì có các chuỗi con như
-
[4], ở đây tối thiểu là 4, tối đa là 4, vì vậy 4 + 4 <=11
-
[4,6], ở đây tối thiểu là 4, tối đa là 6, vì vậy 4 + 6 <=11
-
[4,6,7], ở đây tối thiểu là 4, tối đa là 7, vì vậy 4 + 7 <=11
-
[4,7], ở đây tối thiểu là 4, tối đa là 7, vì vậy 4 + 7 <=11
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
sắp xếp số lượng danh sách
-
m:=10 ^ 9 + 7
-
trái:=0
-
right:=size of nums - 1
-
res:=0
-
trong khi bên trái <=bên phải, thực hiện
-
nếu nums [left] + nums [right]> k thì
-
right:=right - 1
-
-
nếu không,
-
num_inside:=right - left
-
res:=(res + (2 ^ num_inside) mod m) mod m
-
left:=left + 1
-
-
-
trả lại res
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
def solve(nums, k): nums.sort() m = 10**9 + 7 left = 0 right = len(nums) - 1 res = 0 while(left <= right): if nums[left] + nums[right] > k: right -= 1 else: num_inside = right - left res = (res + pow(2, num_inside, m)) % m left += 1 return res nums = [4,6,7,8] k = 11 print(solve(nums, k))
Đầu vào
[4,6,7,8], 11
Đầu ra
4