이 게시물에서는 C++를 사용하여 합이 K보다 작은 하위 배열의 수를 구해보겠습니다. 이 문제에는 배열 arr[]과 정수 K가 있습니다. 이제 합이 K보다 작은 하위 배열을 찾아야 합니다. 아래는 예입니다 −
Input : arr[] = {1, 11, 2, 3, 15} K = 10 Output : 4 {1}, {2}, {3} and {2, 3}
이제 주어진 문제를 해결하기 위해 두 가지 다른 방법을 사용할 것입니다 -
이 방법에서는 모든 하위 배열을 반복하고 그 합계와 합이 k보다 작으면 k와 비교하여 답을 늘립니다.
#include <bits/stdc++.h> using namespace std; int main(){ int arr[] = {1, 11, 2, 3, 15}; // given array int k = 10; // given k int size = sizeof(arr) / sizeof(int); // size of our array. int ans = 0; // counter variable. for(int i = 0; i < size; i++){ // outer loop. int sum = 0; for(int j = i; j < size; j++){ // inner loop. sum = sum + arr[j]; if(sum < k) // comparing with k. ans++; // incrementing our ans if sum is less than k. } } cout << ans << "\n"; return 0; }
4
그러나 이 방법은 시간 복잡도가 매우 높기 때문에(n은 배열의 크기인 O(N*N)) 그다지 좋지 않습니다.
슬라이딩 윈도우 접근 방식을 사용하여 대체 솔루션을 찾아보겠습니다(이는 프로그램의 시간 복잡성을 줄이는 데 도움이 됩니다).
brute force
Strong>과 달리 모든 하위 배열을 반복하지 않습니다. 대신 하위 배열의 합이 k 를 초과하는 경우에만 반복하여 왼쪽 경계를 오른쪽 경계로 이동하고 전체 배열을 탐색할 때까지 반복합니다.
#include <bits/stdc++.h> using namespace std; int main(){ int arr[] = {1, 11, 2, 3, 15}; // given array int k = 10; // given k int size = sizeof(arr) / sizeof(int); // size of our array. int ans = 0; // counter variable. int start = 0; // left border. int end = 0; // right border. int sum = 0; while(end < size && start < size){ // till the whole array is traversed. while(sum >= k && start < end){ sum = sum - arr[start]; start++; } if(end >= start) ans = ans + end - start; sum += arr[end]; end++; } cout << ans << "\n"; return 0; }
4
우리는 Sliding Window Technique을 사용하여 더 큰 제약 조건을 처리할 때 프로그램을 더 빠르고 효율적으로 만듭니다.
이 접근 방식에서는 일반적으로 합계가 k보다 작을 때까지 반복하고 이를 기반으로 답을 증가시킵니다. 이는 합계가 k보다 크거나 같을 때 발생하는 코드의 주요 변경 사항입니다. . 이 경우 k보다 작거나 같거나 합이 k보다 크거나 같을 때까지 왼쪽 경계를 증가시키기 시작합니다. 처리가 더 진행됨에 따라 형성될 수 있는 다른 가능한 하위 배열을 반복합니다. k보다 작은 새 하위 배열의 합이 답에 추가되므로 답이 증가합니다.
이전의 무차별 대입 솔루션과 비교할 때 이 방법은 시간 복잡도가 O(N)이므로 매우 효율적입니다. 여기서 N은 배열의 크기입니다.
이 논문에서는 슬라이딩 윈도우 기법을 사용하여 합이 k보다 작은 하위 배열의 개수를 찾는 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식(사소하고 효율적인)을 배웠습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.
위 내용은 C++로 작성하여 합이 K보다 작은 하위 배열의 수를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!