주어진 정렬 양의 정수와 합계의 nums, 합계가 s (주어진 값)보다 크거나 같은 연속 된 nums 하위 배열의 최소 크기를 찾습니다.
차례
예
입력:
nums [] = {2, 3, 1, 2, 4, 3}
초 = 7
출력:
2 {하위 배열 [4, 3]의 합이 7이고 최소 길이가 있음}
최소 크기 하위 배열 합계에 대한 순진한 접근 방식
위의 문제를 해결하기위한 순진한 접근 방식은 두 개의 중첩 루프를 실행하는 것입니다. 여기서 외부 루프는 하위 배열의 시작 인덱스를 나타내고 내부 루프는 주어진 합계보다 크거나 같은 합계가있는 하위 배열의 끝 인덱스를 찾습니다.
최소 길이를 가진 부분 배열을 답으로 선택합니다.
- ans를 무한대로 초기화하십시오.
- i = 0 ~ n (포함되지 않음)에 대해 루프를 실행합니다. 여기서 n은 배열의 요소 수입니다. 3 단계와 4 단계를 반복합니다.
- 변수 합계를 0으로 초기화합니다. 거짓으로 찾은 부울 변수를 초기화합니다. j = (i + 1) ~ n (포함되지 않음)에 대해 중첩 루프를 실행하고 모든 반복에서 합계가 필요한 합계보다 크거나 같은지 확인하고, 더 큰 경우 true로 설정되고 ans를 최소로 업데이트합니다. ans 및 (j – i)의 경우 (j – i)는이 부분 배열의 길이이며 루프를 벗어납니다. 그렇지 않으면 현재 요소의 값을 합계에 더합니다.
- found가 false 인 경우 ans가 ans의 최소값으로 업데이트되고 (n – i)가 I에서 시작하여 끝나는 부분 배열의 길이 인 경우 합계가 필요한 합계보다 크거나 같은지 확인합니다. 마지막 요소에서.
- ans의 값이 무한이면 필요한 합계가있는 하위 배열을 찾을 수 없으며 0을 반환하고 그렇지 않으면 and를 반환합니다.
JAVA 코드
public class MinimumSizeSubarray {
private static int findMinimumSizeSubarray(int[] nums, int s) {
int n = nums.length;
int ans = Integer.MAX_VALUE;
// Outer loop denotes starting index
for (int i = 0; i < n; i++) {
int sum = nums[i];
boolean found = false;
// Inner loop finds the ending index
for (int j = i + 1; j < n; j++) {
if (sum >= s) {
// Subarray found
int length = j - i;
ans = Math.min(ans, length);
found = true;
break;
}
// Add the current value to sum
sum += nums[j];
}
if (!found) {
// This handles the case of subarray from i to last
if (sum >= s) {
int length = n - i;
ans = Math.min(ans, length);
}
}
}
// Subarray with required sum is not found
if (ans == Integer.MAX_VALUE) {
ans = 0;
}
return ans;
}
public static void main(String[] args) {
int nums[] = new int[] {2, 3, 1, 2, 4, 3};
int sum = 7;
int minSize = findMinimumSizeSubarray(nums, sum);
System.out.println(minSize);
}
}
C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int findMinimumSizeSubarray(int *nums, int s, int n) {
int ans = INT_MAX;
// Outer loop denotes starting index
for (int i = 0; i < n; i++) {
int sum = nums[i];
bool found = false;
// Inner loop finds the ending index
for (int j = i + 1; j < n; j++) {
if (sum >= s) {
// Subarray found
int length = j - i;
ans = std::min(ans, length);
found = true;
break;
}
// Add the current value to sum
sum += nums[j];
}
if (!found) {
// This handles the case of subarray from i to last
if (sum >= s) {
int length = n - i;
ans = std::min(ans, length);
}
}
}
// Subarray with required sum is not found
if (ans == INT_MAX) {
ans = 0;
}
return ans;
}
int main() {
int nums[] = {2, 3, 1, 2, 4, 3};
int sum = 7;
int minSize = findMinimumSizeSubarray(nums, sum, 6);
cout<<minSize<<endl;
return 0;
}
2
최소 크기 부분 배열 합계에 대한 복잡성 분석
시간 복잡성 = 의 위에2)
공간 복잡성 = O (1)
여기서 n은 배열의 요소 수입니다.
최소 크기 하위 배열 합계에 대한 최적의 접근 방식
문제를 해결하는 더 좋은 방법은 ptr1과 ptr2라는 두 포인터를 사용하는 것입니다. 여기서 ptr1은 하위 배열의 시작 인덱스를 나타내고 ptr2는 끝 인덱스를 나타냅니다.
암호알고리즘
- ptr1 및 ptr2를 0 (영)으로 초기화하고 변수 합계를 0 (영)으로 초기화합니다.
- sum의 값이 필요한 합계보다 작지만 ptr2에있는 값을 합계에 더하고 ptr2를 앞으로 이동합니다.
- sum의 값이 필요한 합계보다 크거나 같으면 최소 하위 배열 길이를 업데이트하고 합계에서 ptr1에있는 값을 제거하고 ptr1을 앞으로 이동합니다.
- ptr2이 주어진 배열의 길이보다 작을 때 3 단계와 1 단계를 반복합니다.
- 필요한 합계를 가진 부분 배열이 없으면 0을 반환하고, 그렇지 않으면 최소 길이 부분 배열의 길이를 반환합니다.
JAVA 코드
public class MinimumSizeSubarray {
private static int findMinimumSizeSubarray(int[] nums, int s) {
int n = nums.length;
// Initialize ptr1, ptr2 and sum as 0
int ptr1 = 0, ptr2 = 0, sum = 0;
int ans = Integer.MAX_VALUE;
// While ptr2 is less than n
while (ptr2 < n) {
// While the sum is less than s, add value present at ptr2 to sum and move ptr2 ahead
while (sum < s && ptr2 < n) {
sum += nums[ptr2++];
}
// While sum greater than or equals to s, update the minimum subarray length and remove value
// present at ptr1 from sum and move ptr1 ahead
while (sum >= s && ptr1 < n) {
ans = Math.min(ans, ptr2 - ptr1);
sum -= nums[ptr1++];
}
}
// Subarray with required sum is not found
if (ans == Integer.MAX_VALUE) {
ans = 0;
}
return ans;
}
public static void main(String[] args) {
int nums[] = new int[] {2, 3, 1, 2, 4, 3};
int sum = 7;
int minSize = findMinimumSizeSubarray(nums, sum);
System.out.println(minSize);
}
}
C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int findMinimumSizeSubarray(int *nums, int s, int n) {
// Initialize ptr1, ptr2 and sum as 0
int ptr1 = 0, ptr2 = 0, sum = 0;
int ans = INT_MAX;
// While ptr2 is less than n
while (ptr2 < n) {
// While the sum is less than s, add value present at ptr2 to sum and move ptr2 ahead
while (sum < s && ptr2 < n) {
sum += nums[ptr2++];
}
// While sum greater than or equals to s, update the minimum subarray length and remove value
// present at ptr1 from sum and move ptr1 ahead
while (sum >= s && ptr1 < n) {
ans = std::min(ans, ptr2 - ptr1);
sum -= nums[ptr1++];
}
}
// Subarray with required sum is not found
if (ans == INT_MAX) {
ans = 0;
}
return ans;
}
int main() {
int nums[] = {2, 3, 1, 2, 4, 3};
int sum = 7;
int minSize = findMinimumSizeSubarray(nums, sum, 6);
cout<<minSize<<endl;
return 0;
}
2
최소 크기 부분 배열 합계에 대한 복잡성 분석
시간 복잡성 = O (N)
공간 복잡성 = O (1)
여기서 n은 배열의 요소 수입니다.
