鑑於大小n的正整數數組範圍的平等高效查詢，因此預計找到兩個範圍是否給出作爲查詢是等於或不。如果範圍1中存在的所有元素都出現在範圍2中並且數量相同，則認爲兩個範圍相等。在一個整數數組
實施例：
1 2 5 3 5 1 2
查詢：
[1,3] and [5,7]
[2,4] and [3,5]
數目：
Yes
No
幼稚溶液可以通過以下方式被建議：
1.對於每個查詢，創建存儲每個範圍的數組的兩個副本。
2.然後對它們中的每一個進行排序。 O(n*logn)
3.然後，由元素比較元素並返回true或false。 O(n)
所以解決方案的複雜性是O(q*n*logn)，其中q是查詢的數量。有效解決這個問題有可能嗎？
PS：所有變量的約束條件爲n,q，數組元素爲<=10^5。
雖然可能有其他的方法，以及解決這一個，下面的方法將很好地工作在O（N），以解決這個問題。 （如果查詢出現了x次，那麼O（xN）可以通過緩存查詢結果來優化查詢範圍及其結果）
對於我們的簡化，讓我們命名查詢中的開始和結束元素作爲 range1StartIndex，range2StartIndex，range1EndIndex和range2EndIndex。
（如果兩個範圍的差別都相等，那麼我們需要處理數組元素）。
初始化一個HashMap，讓它命名爲countMap。迭代從range1StartIndex直到range1EndIndex數組，並把在地圖中遇到的每個字符的條目及其occurances的總數。轉到下一步。
迭代從range2StartIndex到range2EndIndex的數組。遇到一個字符時，看看它是否出現在countMap。如果它不存在或者其計數爲0，則返回「否」。如果存在，則將計數減1並移至下一步。
迭代countMap的密鑰，如果任何密鑰的計數大於1，則返回「否」，否則轉到下一步。
回 「是」。出口。
你的意思是'O（q * N）'。但是在這種情況下，也可以看到可能的整數範圍（'<= 10^5'），對於每個查詢，使用logn因子而不是遍歷整個哈希表不是更好嗎？ （點號「4」）。 – yobro97
您可以使用代表範圍的節點構建segemnt樹，幷包含該範圍中數字的哈希碼。只有在節點包含的tge散列碼重新排列查詢的情況下，您才需要進行比較，否則您知道它們不相等。 –
好了，讓我們開始與陣列：1 2 5 3 5 1 2
這個數組有四個不同的元素（我們稱之爲數字d），我們可以預先計算這樣的四個列表：
D[1]: 1 1 1 1 1 2 2
D[2]: 0 1 1 1 1 1 2
D[3]: 0 0 0 1 1 1 1
D[5]: 0 0 1 1 2 2 2
這些包含到該點爲止遇到的每個不同元素的數量。這個清單的大小顯然是d*n。
完成之後，對於每個查詢，您可以通過計算D[E][y]-D[E][x])來簡單檢查每個不同元素E中有多少個範圍爲(x,y)。兩個範圍將包含完全相同的元素iff對於所有不同的元素，這種差異是相同的。
顯然，如果與n相比，不同元素的數量相對較低，則每個查詢的費用爲O(distinct values)，此解決方案效果最佳。
我也省略了幾個相當簡單的優化，就好像兩個範圍的長度不相等，或者如果發現任何差異不同，就提前退出。
更新：
您還可以存儲在同一地圖是這樣的：
D'[1]: 0 5
D'[2]: 1 6
D'[3]: 3
D'[5]: 2 4
此地圖只包含了原始D[]將改變指數。該地圖的大小始終爲n，但現在計算D[E][y] - D[E][x]涉及二進制搜索，它仍然保持每個查詢最低成本的情況。
但它仍然不是短期範圍的查詢的理想選擇，其中每個項目的天真比較會產生更好的結果。
有沒有空間限制？你總是可以爲空間折中時間。 – biziclop
@biziclop ...你可以安全地佔用50MB的空間。 – yobro97