สมมติว่าเรามีรายการที่มีค่าบวกเรียกว่า nums และยังมีจำนวนบวก k ด้วย เราต้องหาความยาวของรายการย่อยที่สั้นที่สุด (อาจว่างเปล่า) ที่เราลบออกจาก nums ได้ ดังนั้นผลรวมขององค์ประกอบที่เหลือหารด้วย k ลงตัว แต่เราไม่สามารถลบรายการทั้งหมดได้ หากไม่มีรายการย่อยที่จะลบ ให้คืนค่า -1
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[5,8,6,3] k =8 ผลลัพธ์จะเป็น 1 เนื่องจากผลรวมปัจจุบันขององค์ประกอบของ [5,8,6,3] เท่ากับ 22 ถ้าเรา ลบรายการย่อย [6] ของความยาว 1 แล้วผลรวมคือ 16 ซึ่งหารด้วย 8 ลงตัว
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- rem :=(ผลรวมขององค์ประกอบทั้งหมดที่มีอยู่ใน nums + k) mod k
- ถ้า rem เหมือนกับ 0 แล้ว
- คืน 0
- n :=ขนาดของ nums
- สันนิษฐาน :=0
- mp :=พจนานุกรม เริ่มต้นเก็บ -1 สำหรับคีย์ 0
- res :=n
- สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
- สันนิษฐาน :=presum + nums[i]
- m :=(presum + k) mod k
- mp[m] :=ฉัน
- ถ้า (m - rem + k) mod k มีอยู่ใน mp แล้ว
- res :=ขั้นต่ำของ res และ (i - mp[(m - rem + k) mod k])
- คืนค่า res หาก res ไม่เหมือนกับ n มิฉะนั้น -1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(nums, k):
rem = (sum(nums) + k) % k
if rem == 0:
return 0
n, presum = len(nums), 0
mp = {0: -1}
res = n
for i in range(n):
presum += nums[i]
m = (presum + k) % k
mp[m] = i
if (m - rem + k) % k in mp:
res = min(res, i - mp[(m - rem + k) % k])
return res if res != n else -1
nums = [5,8,6,3]
k = 8
print(solve(nums, k)) อินพุต
[5,8,6,3], 8
ผลลัพธ์
1
