파이썬을 사용하여 주어진 합계 조건을 만족하는 부분 수열의 수를 찾는 프로그램

<시간/>

nums라는 배열과 다른 값 k가 있다고 가정합니다. 최소 및 최대 요소의 합이 k보다 작거나 같도록 nums의 비어 있지 않은 부분 수열의 수를 찾아야 합니다. 답변이 매우 클 수 있으므로 답변 모드 10^9 + 7을 반환합니다.

따라서 입력이 nums =[4,6,7,8] k =11과 같으면 출력은

와 같은 하위 시퀀스가 있기 때문에 4가 됩니다.

[4], 여기서 최소값은 4, 최대값은 4이므로 4+4 <=11
[4,6], 여기서 최소값은 4이고 최대값은 6이므로 4+6 <=11
[4,6,7], 여기서 최소값은 4이고 최대값은 7이므로 4+7 <=11
[4,7], 여기서 최소값은 4이고 최대값은 7이므로 4+7 <=11

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

목록 번호 정렬
m :=10^9 + 7
왼쪽 :=0
오른쪽 :=숫자 크기 - 1
해상도 :=0
왼쪽 <=오른쪽, 수행
동안
- nums[left] + nums[right]> k이면
  - 오른쪽 :=오른쪽 - 1
- 그렇지 않으면
  - num_inside :=오른쪽 - 왼쪽
  - res :=(res + (2^num_inside) mod m) mod m
  - 왼쪽 :=왼쪽 + 1
반환 해상도

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

예시

def solve(nums, k):
   nums.sort()
   m = 10**9 + 7
   left = 0
   right = len(nums) - 1
   res = 0
   while(left <= right):
      if nums[left] + nums[right] > k:
         right -= 1
      else:
         num_inside = right - left
         res = (res + pow(2, num_inside, m)) % m
         left += 1
   return res
nums = [4,6,7,8]
k = 11
print(solve(nums, k))

입력

[4,6,7,8], 11