주어진 합계로 하위 배열을 찾는 것은 코딩 인터뷰와 경쟁 프로그래밍에서 자주 나타나는 일반적인 문제입니다. 이 문제는 다양한 기술을 사용하여 해결될 수 있으며, 각 기술에는 시간 복잡도와 공간 복잡도에 대한 절충점이 있습니다. 이 기사에서는 Java에서 주어진 합계를 사용하여 하위 배열을 찾는 문제를 해결하는 여러 가지 접근 방식을 살펴보겠습니다.

문제 설명

정수 배열과 목표 합계가 주어지면 배열에서 주어진 합계를 합산하는 연속 하위 배열을 찾습니다. 문제는 두 가지 주요 변형으로 나눌 수 있습니다:

1. 양수가 포함된 하위 배열: 배열에는 양수만 포함됩니다.
2. 혼합 숫자가 포함된 하위 배열: 배열에는 양수와 음수가 모두 포함되어 있습니다.

이러한 변형을 해결하기 위한 다양한 방법을 살펴보겠습니다.

접근 1: 무차별 대입 사용

무차별 접근 방식에는 가능한 모든 하위 배열을 검사하고 그 합계를 계산하여 그 중 목표 합계와 같은 것이 있는지 확인하는 작업이 포함됩니다. 이 접근 방식은 두 변형 모두에서 작동하지만 2차 시간 복잡성으로 인해 대규모 배열에는 비효율적입니다.

구현

public class SubarraySumBruteForce {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int n = arr.length;
    for (int start = 0; start 
산출
Subarray found from index 1 to 3

분석

• 시간 복잡도: 배열을 반복하는 두 개의 중첩 루프로 인해 O(n²).
• 공간 복잡도: O(1) 입력 배열 외에는 추가 공간이 사용되지 않습니다.

접근법 2: 슬라이딩 윈도우 사용

슬라이딩 윈도우 접근 방식은 양수만 포함하는 배열에 효율적입니다. 이 기술에는 목표 합계에 합산되는 요소 창을 유지하는 작업이 포함됩니다. 합계가 목표를 초과할 때까지 요소를 추가하여 창을 확장하고 합계가 목표보다 작거나 같을 때까지 처음부터 요소를 제거하여 창을 축소합니다.

구현

public class SubarraySumSlidingWindow {
  public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
    int start = 0;
    int currentSum = 0;

    for (int end = 0; end  targetSum && start 
산출
Subarray found from index 1 to 3

분석

• 시간 복잡도: O(n), 각 요소는 최대 두 번 처리됩니다.
• 공간 복잡도: O(1) 추가 공간이 필요하지 않습니다.