파이썬에서 합이 k로 나누어 떨어지는 연속적인 부분 수열의 수를 찾는 프로그램

<시간/>

배열 num과 값 k가 있다고 가정합니다. 합이 k로 나누어 떨어지는 연속적인 부분 수열의 수를 찾아야 합니다.

따라서 입력이 k =3 nums =[1,2,3,4,1]과 같으면 하위 시퀀스가 [3], [1,2], [1,2,3이므로 출력은 4가 됩니다. ] 및 [2,3,4].

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

x :=크기가 k이고 0으로 채워지는 배열
x[0] :=1
r:=0, s:=0
숫자 단위의 각 요소에 대해 다음을 수행합니다.
- s :=(s + 요소) 모드 k
- r :=r + x[s]
- x[s] :=x[s] + 1
반환 r

예시

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

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]