在 Java 中計算具有特定算術平均值的子數組
1. 概述
在這個簡短的教程中，我們將學習如何有效地找到具有給定算術平均值的陣列的連續子數組的數量。
我們將從一個簡單的方法開始，以二次時間複雜度 O(n^2) 計算任務。然後，我們將分析其效率低下的原因，並使用前綴和和頻率圖將其最佳化為線性 O(n) 解決方案。
2. 問題陳述
讓我們先了解我們要解決的問題是什麼。
假設我們有一個整數陣列和一個目標平均值，它只是一個整數。現在，我們要計算從輸入數組開始具有特定算術平均值的連續子數組的數量。例如，對於陣列 [5, 3, 6, 2] 和目標平均值 4，輸出應為 3。平均值均為4。
此外，我們希望施加以下約束：
- 此數組最多可包含 100,000 個元素。
- 數組中每個數字的範圍為 [-1,000,000,000, +1,000,000,000]。
- 目標均值在同一範圍內。
讓我們先用暴力方法來解決這個問題。
3. 暴力解決方案
解決這個問題最直接的方法是從兩個巢狀循環開始。一種是迭代子數組的所有可能的索引，另一種是計算子數組的總和並檢查平均值是否等於目標平均值：
static int countSubarraysWithMean(int[] inputArray, int mean) {
int count = 0;
for (int i = 0; i < inputArray.length; i++) {
long sum = 0;
for (int j = i; j < inputArray.length; j++) {
sum += inputArray[j];
if (sum * 1.0 / (j - i + 1) == mean) {
count++;
}
}
}
return count;
}在這裡，我們計算每個子數組的總和和長度以求平均值。如果平均值等於目標平均值，我們就會增加計數。此外，我們乘以浮點數，以便更精確地計算平均值。
無論這個解決方案看起來多麼簡單，它的效能都不高。當談論演算法複雜度時，我們通常對時間複雜度感興趣。這種暴力解法的時間複雜度為O(n^2)，效率較低。事實上，對於 10 萬個元素的輸入約束，我們需要執行 100 億次操作，這太慢了。
讓我們找到一個更有效的替代解決方案。
4. 線性解
在繼續之前，我們需要了解兩個關鍵思想，以將解決方案最佳化為線性時間複雜度。
4.1.了解前綴和和頻率圖
首先，前綴和的思想允許我們在 O(1) 時間內計算任何子數組的和。其次，頻率圖的概念可以幫助我們透過追蹤某些值的頻率來對子數組進行計數。
現在，假設我們有一個輸入數組X和一個目標平均值S 。我們定義兩個陣列來表示輸入陣列的前綴和和調整後的前綴和：
P[i] = X[0] + X[1] + ... + X[i] (prefix sum array)
ADJUSTED_PREFIX_SUM_ARRAY[i] = P[i] - S * i (adjusted prefix sum array)然後，對於任何具有平均值S子數組[i, j] ，我們定義Q ：
ADJUSTED_PREFIX_SUM_ARRAY[j] = P[j] - S * j
= (P[j] - P[i-1]) - S * (j - (i-1))
= (sum of subarray [i, j]) - (length of subarray [i, j]) * S
= ADJUSTED_PREFIX_SUM_ARRAY[i-1]ADJUSTED_PREFIX_SUM_ARRAY計算子數組[i, j]的總和，並用平均值S減去子數組的預期總和。現在，利用這些值，我們可以透過計算索引(i-1, j)的數量來計算平均為S的子數組的數量，其中ADJUSTED_PREFIX_SUM_ARRAY[j] = ADJUSTED_PREFIX_SUM_ARRAY[i-1] 。
這裡的關鍵見解是，如果我們在ADJUSTED_PREFIX_SUM_ARRAY數組中找到具有相同值的兩個索引，則這些索引之間的子數組（不包括較早的索引）的平均值為S 。這意味著從i到j子數組具有精確的均值S ：
(P[j] - P[i-1]) - S * (j - (i-1)) = 0這個子數組等價於這個：
P[j] - S * j = P[i-1] - S * (i-1)左側是ADJUSTED_PREFIX_SUM_ARRAY[j] ，右邊是ADJUSTED_PREFIX_SUM_ARRAY[i-1] 。
讓我們來實現這個。
4.2. Java實作
讓我們先建立兩個陣列：
static int countSubarraysWithMean(int[] inputArray, int mean) {
int n = inputArray.length;
long[] prefixSums = new long[n+1];
long[] adjustedPrefixes = new long[n+1];
// More code
}在這裡，我們使用long值而不是整數，以避免計算包含大值的子數組總和時溢位。然後，我們計算前綴和數組P和調整後的前綴和數組Q ：
for (int i = 0; i < n; i++) {
prefixSums[i+1] = prefixSums[i] + inputArray[i];
adjustedPrefixes[i+1] = prefixSums[i+1] - (long) mean * (i+1);
}接下來，我們建立一個頻率圖來計算子數組的數量並傳回總計數：
Map<Long, Integer> count = new HashMap<>();
int total = 0;
for (long adjustedPrefix : adjustedPrefixes) {
total += count.getOrDefault(adjustedPrefix, 0);
count.put(adjustedPrefix, count.getOrDefault(adjustedPrefix, 0) + 1);
}
return total;對於 prefixes 數組中的每個調整後的前綴，我們將總計數增加到目前為止看到的adjustedPrefixes的頻率。如果頻率圖不包含前綴，我們回傳0 。
此解的時間複雜度為 O(n)。我們運行了兩次for迴圈。首先，我們計算前綴和和調整後的前綴和，第二次，我們計算子數組的數量。空間複雜度也是 O(n)，因為我們使用兩個大小為n的陣列和一個可以儲存n條目的頻率圖。
5. 結論
在本文中，我們解決了計算具有給定算術平均值的子數組的問題。首先，我們實現了時間複雜度為 O(n^2) 的強力解。然後，我們使用前綴和和頻率圖將其最佳化為線性時間複雜度 O(n)。
像往常一樣，完整的程式碼可以在 GitHub 上找到。