파이썬의 K 접두사

<시간/>

숫자 nums와 정수 k의 목록이 있다고 가정하고 nums[0] + nums[1] + ... + nums[i] ≤ k일 때 가능한 최대 i를 찾아야 합니다. 유효한 i가 없으면 -1을 반환합니다.

따라서 입력이 nums =[4, -7, 5, 2, 6], k =5와 같으면 출력은 3이 되고 인덱스는 4+(-7)+5+2를 더하는 것처럼 3이 됩니다. =4, 이것은 k보다 작습니다. 마지막 요소를 추가하면 더 이상 k보다 작지 않으므로 인덱스는 3입니다.

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

범위 1에서 숫자 - 1까지의 i에 대해
- 숫자[i] :=숫자[i] + 숫자[i-1]
-1에서 -1 사이의 범위 크기에 있는 i에 대해 1만큼 감소, do
- 숫자[i]<=k이면
  - 반환
반환 -1

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

예시

class Solution:
   def solve(self, nums, k):
      for i in range(1,len(nums)):
         nums[i]+=nums[i-1]
         for i in range(len(nums)-1,-1,-1):
            if nums[i]<=k:
                return i
      return -1
ob = Solution()
nums = [4, -7, 5, 2, 6]
k = 5
print(ob.solve(nums, k))

입력

[4, -7, 5, 2, 6], 5