nums라고 하는 양수 값이 있고 양수 k도 있는 목록이 있다고 가정합니다. 나머지 요소의 합이 k로 나눌 수 있도록 num에서 삭제할 수 있는 가장 짧은 하위 목록(비어 있을 수 있음)의 길이를 찾아야 합니다. 그러나 전체 목록을 제거할 수는 없습니다. 삭제할 하위 목록이 없으면 -1을 반환합니다.
따라서 입력이 nums =[5,8,6,3] k =8과 같으면 [5,8,6,3] 요소의 현재 합이 22이기 때문에 출력은 1이 됩니다. 길이가 1인 하위 목록 [6]을 제거하면 합계는 16이며 8로 나눌 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- rem :=(nums + k에 있는 모든 요소의 합) mod k
- rem이 0과 같으면
- 0을 반환
- n :=숫자 크기
- 추정 :=0
- mp :=사전, 초기에 키 0에 대해 -1을 저장
- res :=n
- 0 ~ n - 1 범위의 i에 대해
- presum :=추정 + 숫자[i]
- m :=(추정 + k) 모드 k
- mp[m] :=나
- 만약 (m - rem + k) mod k가 mp에 있으면
- res :=res의 최소값 및 (i - mp[(m - rem + k) mod k])
- res가 n과 같지 않으면 res를 반환하고 그렇지 않으면 -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