指定された合計を持つ部分配列を見つけることは、コーディング面接や競技プログラミングで頻繁に現れる一般的な問題です。この問題はさまざまな手法を使用して解決できますが、それぞれの手法には時間の複雑さと空間の複雑さに関する独自のトレードオフがあります。この記事では、Java で指定された合計を持つ部分配列を見つける問題を解決するための複数のアプローチを検討します。

問題ステートメント

整数の配列と目標合計が与えられた場合、合計が指定された合計になる配列内の連続部分配列を見つけます。この問題は 2 つの主なバリエーションに分けられます:

1. 正の数値を含むサブ配列: 配列には正の数値のみが含まれます。
2. 混合数値を含むサブ配列: 配列には正の数値と負の数値の両方が含まれます。

これらの亜種を解決するためのさまざまな方法を検討してみましょう。

アプローチ 1: ブルート フォースを使用する

ブルート フォース アプローチでは、考えられるすべてのサブ配列をチェックし、それらの合計を計算して、それらのいずれかがターゲットの合計と等しいかどうかを確認します。このアプローチは両方のバリアントで機能しますが、二次時間計算量のため、大規模な配列では非効率的です。

実装

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

分析

• 時間計算量: 2 つのネストされたループが配列を反復処理するため、O(n²)。
• Space Complexity: 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) (各要素は最大 2 回処理されるため)。
• スペースの複雑さ: O(1) 追加のスペースは必要ないため。