최소 크기 부분 배열 합계

난이도 중급
자주 묻는 질문 아마존 Facebook 골드만 삭스 구글 Microsoft
배열 이진 검색 두 포인터조회수 75

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

주어진 정렬 양의 정수와 합계의 nums, 합계가 s (주어진 값)보다 크거나 같은 연속 된 nums 하위 배열의 최소 크기를 찾습니다.

입력:
nums [] = {2, 3, 1, 2, 4, 3}
초 = 7
출력:
2 {하위 배열 [4, 3]의 합이 7이고 최소 길이가 있음}

최소 크기 부분 배열 합계

최소 크기 하위 배열 합계에 대한 순진한 접근 방식

위의 문제를 해결하기위한 순진한 접근 방식은 두 개의 중첩 루프를 실행하는 것입니다. 여기서 외부 루프는 하위 배열의 시작 인덱스를 나타내고 내부 루프는 주어진 합계보다 크거나 같은 합계가있는 하위 배열의 끝 인덱스를 찾습니다.
최소 길이를 가진 부분 배열을 답으로 선택합니다.

  1. ans를 무한대로 초기화하십시오.
  2. i = 0 ~ n (포함되지 않음)에 대해 루프를 실행합니다. 여기서 n은 배열의 요소 수입니다. 3 단계와 4 단계를 반복합니다.
  3. 변수 합계를 0으로 초기화합니다. 거짓으로 찾은 부울 변수를 초기화합니다. j = (i + 1) ~ n (포함되지 않음)에 대해 중첩 루프를 실행하고 모든 반복에서 합계가 필요한 합계보다 크거나 같은지 확인하고, 더 큰 경우 true로 설정되고 ans를 최소로 업데이트합니다. ans 및 (j – i)의 경우 (j – i)는이 부분 배열의 길이이며 루프를 벗어납니다. 그렇지 않으면 현재 요소의 값을 합계에 더합니다.
  4. found가 false 인 경우 ans가 ans의 최소값으로 업데이트되고 (n – i)가 I에서 시작하여 끝나는 부분 배열의 길이 인 경우 합계가 필요한 합계보다 크거나 같은지 확인합니다. 마지막 요소에서.
  5. 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는 끝 인덱스를 나타냅니다.

암호알고리즘

  1. ptr1 및 ptr2를 0 (영)으로 초기화하고 변수 합계를 0 (영)으로 초기화합니다.
  2. sum의 값이 필요한 합계보다 작지만 ptr2에있는 값을 합계에 더하고 ptr2를 앞으로 이동합니다.
  3. sum의 값이 필요한 합계보다 크거나 같으면 최소 하위 배열 길이를 업데이트하고 합계에서 ptr1에있는 값을 제거하고 ptr1을 앞으로 이동합니다.
  4. ptr2이 주어진 배열의 길이보다 작을 때 3 단계와 1 단계를 반복합니다.
  5. 필요한 합계를 가진 부분 배열이 없으면 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은 배열의 요소 수입니다.

참조

균열 시스템 설계 인터뷰
Translate »