Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

파이썬에서 합이 k의 배수인 크기가 2 이상인 하위 목록을 찾는 프로그램

<시간/>

nums라고 하는 음수가 아닌 숫자 목록과 또 다른 양수 값 k가 있다고 가정합니다. 합이 k의 배수인지 아닌지 길이가 2 이상인 하위 목록이 있는지 확인해야 합니다.

따라서 입력이 nums =[12, 6, 3, 4] k =5와 같으면 하위 목록이 [12, 3] 합계가 15이고 5로 나눌 수 있으므로 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • 합계 :=0
  • m :=새 지도
  • m[0] :=-1
  • 0에서 숫자 크기 범위의 i에 대해
    • 합계 :=합 + 숫자[i]
    • sum :=합계 모드 k
    • 합계가 m에 있으면
      • i - m[sum]>=2이면
        • 참 반환
    • 그렇지 않으면
      • m[sum] :=나
  • 거짓을 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, nums, k):
      sum = 0
      m = {}
      m[0] = -1
      for i in range(0, len(nums)):
         sum += nums[i]
         sum %= k
         if sum in m:
            if i - m[sum] >= 2:
               return True
         else:
            m[sum] = i
      return False
ob = Solution()
nums = [12, 6, 3, 4]
k = 5
print(ob.solve(nums, k))

입력

[12, 6, 3, 4], 5

출력

True