找到一個數組的子集，使子集中的元素有一個共同的差異

Question

我準備面試時遇到了一個問題。 給定一個整數數組作爲輸入。 我們已經找到了一個可能的子集，使得數組中的元素有一個共同的區別。 例如對於 考慮輸入數組爲{1,3,7,10,11} 然後輸出應該是{3,7,11}。 數組中的元素總是按遞增順序排列。 我想找到所有的子集並尋找解決方案。 但是如果輸入數組的大小太大，那會導致我的程序運行速度變慢。 任何人都可以幫我解決這個問題嗎？

Answer 1

據我所知，你想從數組中提取可能的子集，使得每兩個連續的數字越來越多地具有相同的差異值。

這裏是我的算法：

1. 刪除重複。
   
2. 強制安排遞增。
   
3. 保留一個哈希表，其中的差值作爲鍵和列表的列表作爲值。
   
4. 循環訪問數組，在散列表中更新/添加一個等於當前兩個連續數字之間差值的密鑰，並將列表添加到包含這兩個數字的值（列表列表）中。
   
5. 循環後，創建一個數組。遍歷哈希表，每次向數組本身添加一個元素，該數組本身就是一個數組：將所有嵌套列表合併到手頭的值中。這是包含所有可能子集的數組。

這裏是Python中的可能的實現：

from itertools import chain 
def find_subsets (array): 
    table = dict() 
    last = array[-1] 
    for num in sorted (set (array), False)[1:]: 
     diff = last - num 
     table[diff].append([num, last]) 
     last = num 
    return [list(chain(v)) for k, v in table] 

請試試這個代碼，如果錯誤的糾正。我匆忙寫了這篇文章。