สมมติว่าเรามีจำนวนอาร์เรย์และค่า p อื่น เราจะลบอาร์เรย์ย่อยที่เล็กที่สุด (ไม่ใช่อาร์เรย์ทั้งหมด) เพื่อให้ผลรวมของค่าที่เหลือหารด้วย p ลงตัว เราต้องหาความยาวของ subarray ที่เล็กที่สุดที่เราจำเป็นต้องลบ หากไม่มี subarray นั้นให้คืนค่า -1
ดังนั้น หากอินพุตเท่ากับ nums =[8,2,6,5,3] p =7 ผลลัพธ์จะเป็น 1 เพราะหากเราลบ 3 ผลรวมทั้งหมดจะเป็น 21 และหารด้วย 7 ลงตัว
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- แทน :=อินฟินิตี้
- s :=(ผลรวมขององค์ประกอบทั้งหมดเป็น nums) mod p
- d :=แผนที่มีคู่คีย์-ค่า {0:-1}
- สุดยอด :=0
- ถ้า s เหมือนกับ 0 แล้ว
- คืน 0
- สำหรับ i ในช่วง 0 ถึงขนาดของ nums ให้ทำ
- น้ำเชื้อ :=น้ำเชื้อ + nums[i]
- r :=cum mod p
- ถ้า (r-s)mod p มีอยู่ใน d แล้ว
- ans :=ขั้นต่ำของ ans และ i - d[(r-s) mod p]
- d[r] :=ฉัน
- ส่งคืน ans if ans <ขนาดของ nums มิฉะนั้น -1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(nums, p):
ans = float("inf")
s = sum(nums) % p
d = {0:-1}
cum = 0
if s == 0:
return 0
for i in range(len(nums)):
cum+=nums[i]
r = cum%p
if (r-s)%p in d:
ans = min(ans, i-d[(r-s)%p])
d[r] = i
return ans if ans<len(nums) else -1
nums = [8,2,6,5,3]
p = 7
print(solve(nums, p)) อินพุต
[8,2,6,5,3], 7
ผลลัพธ์
1
