다양한 접근 방식을 사용하여 Java에서 주어진 합계를 가진 하위 배열

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

문제 설명

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

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

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

접근 방법 1: 무차별 대입 사용

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

구현

출력

분석

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

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

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

구현

출력

분석

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

위 내용은 다양한 접근 방식을 사용하여 Java에서 주어진 합계를 가진 하위 배열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!