在 Java 中求最大零和子數組的長度
1. 概述
尋找總和為零的最大子數組是一個經典問題，可以使用HashMap有效解決。
在本教程中，我們將詳細介紹在 Java 中解決此問題的詳細逐步方法，並介紹暴力比較方法。
2. 問題陳述
給定一個整數數組，我們想要找出總和為 0 的最大子數組的長度。
輸入： arr = [4, -3, -6, 5, 1, 6, 8]
輸出： 4
解釋：數組從第 0 個索引到第 3 個索引的總和為0 。
3. 蠻力方法
蠻力方法涉及檢查所有可能的子數組以查看它們的總和是否為零並追蹤此類子數組的最大長度。
我們先看一下實現，然後逐步理解：
public static int maxLen(int[] arr) {
int maxLength = 0;
for (int i = 0; i < arr.length; i++) {
int sum = 0;
for (int j = i; j < arr.length; j++) {
sum += arr[j];
if (sum == 0) {
maxLength = Math.max(maxLength, j - i + 1);
}
}
}
return maxLength;
}讓我們回顧一下這段程式碼：
- 首先，我們將變數
maxLength初始化為0 - 然後，使用兩個巢狀循環產生所有可能的子數組
- 對於每個子數組，計算
sum - 如果
sum為0，如果目前子數組長度超過maxLength則更新maxLength
現在，我們來討論一下時間複雜度和空間複雜度。我們使用兩個巢狀循環，每個循環都遍歷數組，導致時間複雜度為二次方。所以，時間複雜度是O(n^2) 。由於我們只使用了一些額外的變量，因此空間複雜度為O(1) 。
4.使用HashMap最佳化方法
在這種方法中，我們在迭代數組時維護元素的累積和。我們使用HashMap來儲存累積和及其索引。如果之前看到累積和，則表示前一個索引和目前索引之間的子數組的總和為0 。因此，我們不斷追蹤此類子數組的最大長度。
我們先看一下實作：
public static int maxLenHashMap(int[] arr) {
HashMap<Integer, Integer> map = new HashMap<>();
int sum = 0;
int maxLength = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (sum == 0) {
maxLength = i + 1;
}
if (map.containsKey(sum)) {
maxLength = Math.max(maxLength, i - map.get(sum));
}
else {
map.put(sum, i);
}
}
return maxLength;
}讓我們透過視覺來理解這段程式碼：
- 首先，我們初始化一個
HashMap來儲存sum和及其索引 - 然後，我們用 sum
0來初始化子數組的累積和和最大長度變數 - 我們遍歷數組並更新
sum - 我們檢查
sum和是否為0。如果是，我們更新最大長度 - 如果
sum和已經在HashMap中，我們計算子數組的長度，如果它大於當前的最大值，則更新最大長度 - 如果
sum和不在HashMap中，我們將其及其索引添加到HashMap
現在我們將考慮我們在開始時提到的範例並進行一次演練：
如果我們考慮時間和空間複雜度，我們遍歷數組一次， HashMap的每個操作（插入和查找）平均為O(1) 。所以，時間複雜度是O(n) 。在最壞的情況下， HashMap儲存所有的累積和。因此，空間複雜度為O(n) 。
5. 比較
暴力方法的時間複雜度為O(n^2) ，這使得它對大型陣列來說效率低。使用HashMap最佳化方法的時間複雜度為O(n) ，使其更適合大型資料集。
暴力方法使用O(1)空間，而最佳化方法由於HashMap而使用O(n)空間。需要在時間效率和空間使用之間進行權衡。
六、結論
在本文中，我們看到使用HashMap來追蹤累積和可以讓我們有效地找到總和為零的最大子陣列。這種方法確保我們可以在線性時間內解決問題，使其可擴展用於大型陣列。
蠻力方法雖然在概念上較簡單，但由於其二次時間複雜度，對於大輸入大小不可行。
與往常一樣，所有這些範例的原始程式碼都可以在 GitHub 上取得。