สมมติว่าเรามีตัวเลขอาร์เรย์และค่า k เราต้องหาจำนวนลำดับที่ต่อเนื่องกันซึ่งผลรวมหารด้วย k ลงตัว
ดังนั้น ถ้าอินพุตเป็นเหมือน k =3 nums =[1,2,3,4,1] ผลลัพธ์จะเป็น 4 เพราะส่วนย่อยคือ [3], [1,2], [1,2,3 ] และ [2,3,4].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- x :=อาร์เรย์ขนาด k และเติม 0
- x[0] :=1
- r:=0, s:=0
- สำหรับแต่ละองค์ประกอบเป็น nums ทำ
- s :=(s + elem) mod k
- r :=r + x[s]
- x[s] :=x[s] + 1
- คืนสินค้า
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(k, nums):
x = [0]*k
x[0] = 1
r=s=0
for elem in nums:
s = (s+elem) % k
r += x[s]
x[s] += 1
return r
k = 3
nums = [1,2,3,4,1]
print(solve(k, nums)) อินพุต
3, [1,2,3,4,1]
ผลลัพธ์
4
