我碰到
如上圖所示，它得到包含元素的子陣列
[1, 2]
[1, 2, 1]
[2, 1]
[2, 1, 2]
[1, 2]
[2, 3]
但是我不明白如何使用元素獲取子陣列 {1, 2, 1, 2}
因為，恰好由兩個元素形成的子陣列是：-
[1, 2]
[1, 2, 1]
[2, 1]
[2, 1, 2]
[1, 2]
[2, 3]
[1, 2, 1, 2]
這是我的解決方案
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] A = {1, 2, 1, 2, 3};
int K = 2;
HashMap<Integer, Integer> map = new HashMap<>();
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0;i<A.length; i ){
map.put(A[i], map.getOrDefault(A[i], 0) 1);
list.add(A[i]);
if(map.size() == K) System.out.println(list);
while(map.get(list.get(0)) > 1 || map.size() > K){
map.put(list.get(0), map.get(list.get(0)) - 1);
if (map.get(list.get(0)) == 0) map.remove(list.get(0));
list.remove(0);
if(map.size() == K) System.out.println(list);
}
}
}
}
這給出了輸出
[1, 2]
[1, 2, 1]
[2, 1]
[2, 1, 2]
[1, 2]
[2, 3]
但我不明白如何{1, 2, 1, 2}使用這種方法。我哪里錯了！
uj5u.com熱心網友回復：
我注意到的第一件事是，您參考的兩個問題都是關于找到具有 K 個唯一元素的子陣列的計數，而不是像您在此處嘗試執行的那樣列印它們。這種差異會影響閱讀和理解代碼的方式，值得指出:)
至于如何將 [1, 2, 1, 2] 包含在結果中，我查看了您包含的GeeksForGeeks鏈接。我從中得到的主要觀點是您的代碼中似乎缺少的內容是prefix的想法。
如您上面發布的圖片所示，演算法的主要邏輯跟蹤滑動視窗。由于該演算法正在尋找不超過 K 個元素的子陣列，因此它在回圈的每次迭代結束時將滑動視窗的大小限制為 K。因此，需要有一種方法來跟蹤元素重復的情況 - 否則，該演算法不會計算總元素超過 K 個的子陣列，而是計算 K 個唯一元素的重復項。
這就是前綴的用武之地。 正如您在上面發布的圖片中看到的，該演算法包括每次滑動視窗增加到大于 K 的大小時檢查其內容。
如果視窗因為包含重復元素而具有超過 K 個元素，則第一個元素將作為“前綴”分隔（如果已經存在，則將其添加到其中）。這將視窗的大小限制為 K，同時還跟蹤前綴仍然是子陣列的有效部分。然后隨著視窗繼續滑動，跟蹤該前綴的大小。對于演算法找到的每個新的有效子陣列，它將有效子陣列的總數增加 1（對于新的 K 長度子陣列）加上前綴的長度。這是因為可以從前綴構建的每個子陣列，當與當前滑動視窗結合時，仍然是 K 個唯一元素的子陣列。這就是演算法中計算[1, 2, 1, 2]的方式——當i = 5時，“滑動視窗”為[1, 2]（輸入串列中每個數字的第二次出現），前綴大小為 2 - 表示 [1, 2] 的串列（輸入串列中每個數字的第一次出現）。因此，演算法中此時有效子陣列的總數為 3 - [1, 2]（滑動視窗），[2, 1, 2]（滑動視窗以前綴的最后一個元素為前綴），以及[1, 2, 1, 2]（滑動視窗前面加上了整個前綴）。
如果視窗有超過 K 個元素，因為每個元素都是唯一的，那么演算法知道它到達了一個有效子陣列的末尾——當前視窗和任何在它前面加上部分前綴的子陣列總是有更多比K個獨特的元素。此時，演算法會重置前綴，將視窗縮小為 K 個元素，然后繼續處理。
uj5u.com熱心網友回復：
這是一種線性方法。
使用兩個索引，一個用于計算索引之間不同元素數量的計數器，以及一個計數映射（從元素到索引之間的計數）。
When the number of distinct elements is <= your target:
1) print if you have equality
2) increment the right index
3) update the counting map
4) increment the number of distinct elements if step 3 took something from zero or uninitialized to 1.
When the number of distinct elements is > your target:
1) increment the left index
2) update the counting map
3) decrement the number of distinct elements of step 2 to something from 1 to zero.
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313569.html