Chương trình tìm số lượng tối đa các mảng con không chồng chéo với tổng bằng đích bằng Python

Giả sử chúng ta có một nums mảng và một giá trị khác được gọi là target. Bây giờ chúng ta phải tìm số lượng tối đa các mảng con không chồng chéo không trống để tổng các giá trị trong mỗi mảng con khác nhau giống với đích.

Vì vậy, nếu đầu vào giống như nums =[3,2,4,5,2,1,5] target =6, thì đầu ra sẽ là 2 vì có hai mảng con [2,4] và [1,5] có tổng bằng 6.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• t:=một tập hợp mới với một phần tử 0

• tạm thời:=0

• ans:=0

• đối với mỗi tôi trong nums, hãy thực hiện

  • temp:=temp + i

  • trước:=temp - target

  • nếu trước là t, thì

    • ans:=ans + 1

    • t:=một tập hợp mới với temp phần tử duy nhất

  • nếu không,

    • chèn tạm thời vào t

• trả lại ans

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, target):
   t = set([0])
   temp = 0
   ans=0
   for i in nums:
      temp += i
      prev = temp-target
      if prev in t:
         ans += 1
         t = set([temp])
      else:
         t.add(temp)
   return ans
nums = [3,2,4,5,2,1,5]
target = 6
print(solve(nums, target))

Đầu vào

"poput","vwput",9

Đầu ra

2