找到一个数组的子集，使子集中的元素有一个共同的差异

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] 

请试试这个代码，如果错误的纠正。我匆忙写了这篇文章。