배열 num과 다른 값 p가 있다고 가정하고 나머지 값의 합이 p로 나눌 수 있도록 가장 작은 하위 배열(전체 배열이 아님)을 제거합니다. 제거해야 하는 가장 작은 부분배열의 길이를 찾아야 합니다. 그런 부분배열이 없으면 -1을 반환합니다.
따라서 입력이 nums =[8,2,6,5,3] p =7과 같으면 출력은 1이 됩니다. 왜냐하면 3을 제거하면 총합은 21이 되고 7로 나눌 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- ans :=무한대
- s :=(nums에 있는 모든 요소의 합) mod p
- d :=키-값 쌍 {0:-1}을 포함하는 맵
- 정액 :=0
- s가 0과 같으면
- 0을 반환
- 0~숫자 크기 범위의 i에 대해
- 정액 :=정액 + 숫자[i]
- r :=정액 모드 p
- (r-s)mod p가 d에 있으면
- ans :=as 및 i의 최소값 - d[(r-s) mod p]
- d[r] :=나
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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