さまざまなアプローチによる Java での指定された合計を持つ部分配列

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

問題の声明

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

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

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

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

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

実装

リーリー

出力

リーリー

分析

• 時間計算量: 2 つのネストされたループが配列を反復処理するため、O(n²)。
• 空間複雑さ: 入力配列を超えて追加の空間が使用されないため、O(1)。
アプローチ 2: スライディング ウィンドウを使用する

スライディング ウィンドウ アプローチは、正の数のみを含む配列に対して効率的です。この手法には、合計が目標合計に達する要素のウィンドウを維持することが含まれます。合計が目標を超えるまで要素を追加するとウィンドウが拡張され、合計が目標以下になるまで最初から要素を削除するとウィンドウが縮小されます。

実装

リーリー

出力

リーリー

分析

時間計算量: 各要素は最大 2 回処理されるため、O(n)
• 空間複雑さ:
追加の空間は必要ないため、O(1)。

以上がさまざまなアプローチによる Java での指定された合計を持つ部分配列の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。