สมมติว่าเรามีจำนวนอาร์เรย์ที่มีองค์ประกอบบวก n หากเราคำนวณผลรวมของอาร์เรย์ย่อยที่ต่อเนื่องกันของ nums ที่ไม่ว่างเปล่าทั้งหมด แล้วจัดเรียงตามแบบที่ไม่ลดลง โดยสร้างอาร์เรย์ใหม่ของตัวเลข n*(n+1)/2 เราต้องหาผลรวมของตัวเลขจากดัชนีซ้ายไปขวาดัชนี (ดัชนี 1 รายการ) รวมอยู่ในอาร์เรย์ใหม่ คำตอบอาจมีขนาดใหญ่มาก ดังนั้นส่งคืนผลลัพธ์ modulo 10^9 + 7.
ดังนั้น หากอินพุตเท่ากับ nums =[1,5,2,6] ซ้าย =1 ขวา =5 ผลลัพธ์จะเป็น 20 เพราะในที่นี้ ผลรวมของอาร์เรย์ย่อยทั้งหมดคือ 1, 5, 2, 6, 6, 7, 8 , 8, 13, 14 ดังนั้นหลังจากเรียงลำดับแล้ว พวกมันคือ [1,2,5,6,6,7,8,8,13,14] ผลรวมขององค์ประกอบจากดัชนี 1 ถึง 5 คือ 1+5+2 +6+6 =20.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ม :=10^9 + 7
-
n :=ขนาดของ nums
-
a:=รายการใหม่
-
สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ
-
สำหรับ j ในช่วง i ถึง n - 1 ทำ
-
ถ้าฉันเหมือนกับ j แล้ว
-
ใส่ nums[j] ต่อท้าย a
-
-
มิฉะนั้น
-
แทรก ((nums[j] + องค์ประกอบสุดท้ายของ a) mod m) ที่ส่วนท้ายของ a
-
-
-
-
เรียงลำดับรายการ
-
sm:=ผลรวมขององค์ประกอบทั้งหมดของ a[จากดัชนีซ้าย-1 ไปขวา])
-
ส่งคืน sm mod m
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
def solve(nums, left, right): m = 10**9 + 7 n = len(nums) a=[] for i in range(n): for j in range(i,n): if i==j: a.append(nums[j]) else: a.append((nums[j]+a[-1])%m) a.sort() sm=sum(a[left-1:right]) return sm % m nums = [1,5,2,6] left = 1 right = 5 print(solve(nums, left, right))
อินพุต
[1,5,2,6], 1, 5
ผลลัพธ์
20
