问题陈述：
在一个数组，从中找出k个数（每个数不能重复取。数组中同一个值有多个，可以取多个），使得和为零。找出所有这样的组合，要求没有重复项（只要值不同即可，不要求在原数组中的index不同）
解法：
2 sum 用hash table做，可以时间O(n)，空间O（n），
2 sum 如果用sort以后，在前后扫描，可以时间O(nlogn + n) = O(nlogn)，空间O(1)
2 sum 用hash table做的好处是快，但是等于是利用了不用排序的特点。排序的办法，在高维度（也就是k sum问题，k>2）的时候，nlogn就不是主要的时间消耗成分，也就更适合2sum的sort后双指针扫描查找的办法。
那么，对于k sum， k>2的，如果用sort的话， 可以 对 n-2的数做嵌套循环，因为已经sort过了，最后剩下的两维用2 sum的第二个办法， 时间是O(nlogn + n^(k-2) * n) = O(n^(n-1))，空间O(1)。 但是这样跟纯嵌套循环没有什么区别，只是最后一层少了一个因子n。有什么办法能优化？
就是说，对于 k sum (k>2) 问题 （一个size为n的array, 查找k个数的一个tuple，满足总和sum为0）， 有没有时间复杂度在O(n^(k-2))的办法？
之前常规的一层一层剥离，n的次数是递增的。只有在最后一层，还有两个维度的时候，时间开销上减少一个n的因子，但是这样时间开销还是太多
我们可以通过对问题分解来解决
举个例子
...-5，-4，-3，-2，-1, 0，1, 2, 3, 4, 5.... 要找 4 sum = 0
那么先分解
4 分成 2 sum + 2 sum 来解决，但是这里的子问题2 sum没有sum=0的要求，是保留任何中间值。只有当子问题的2 sum解决以后，回归原问题的时候，我们才又回归原始的2 sum问题，这时候sum=0
子问题，空间和时间消耗，都是O(n^2)
回归大问题，时间消耗，是O(n^2)
假设k sum中 k = 2^m, 那么一共有m层，会有m次分解
分解到最底层，时间空间消耗 从 原始O(n)变为新的O(n^2)
分解到次底层，时间空间消耗 从 O(n^2)变为新的O((n^2)^2)
...
到达最顶层，时间空间消耗就都变成了O(n^(2*m)) = O(n^(2logk))
和之前的方法O(n^(k-1))相比，O(n^(2logk))的时间是少了很多，但是空间消耗却很大。
因为子问题无法确定把哪一个中间结果留下，那么就需要把子问题的结果全部返回，到最后，空间消耗就很大了。整体效果算是空间换时间吧。
通过 问题的分解 + hashtable的运用，能明显减少时间消耗， 但是空间消耗变大是个问题。比如说，如果有10^6的int类型数组，我如果用这个hashtable的办法，就要有10^12的pair，这就有10T以上的空间消耗。
问题的分解是个很好的思路，但是中间值得保留迫使空间消耗增大，这和用不用hashtable倒没有很大关系，只是说，如果不用hashtable，时间消耗会更大。
另外，还有一些题目的变形，比如如果要求所有组合，满足
sum < k,
sum = k,
sum > k,
或者是 closest to k
遇到这些变形的时候，hashtable的做法就显得乏力了，但是嵌套循环的方式却仍是可行的。尤其是对closest to k这种非确定性的要求。
在一个数组，从中找出k个数（每个数不能重复取。数组中同一个值有多个，可以取多个），使得和为零。找出所有这样的组合，要求没有重复项（只要值不同即可，不要求在原数组中的index不同）
解法：
2 sum 用hash table做，可以时间O(n)，空间O（n），
2 sum 如果用sort以后，在前后扫描，可以时间O(nlogn + n) = O(nlogn)，空间O(1)
2 sum 用hash table做的好处是快，但是等于是利用了不用排序的特点。排序的办法，在高维度（也就是k sum问题，k>2）的时候，nlogn就不是主要的时间消耗成分，也就更适合2sum的sort后双指针扫描查找的办法。
那么，对于k sum， k>2的，如果用sort的话， 可以 对 n-2的数做嵌套循环，因为已经sort过了，最后剩下的两维用2 sum的第二个办法， 时间是O(nlogn + n^(k-2) * n) = O(n^(n-1))，空间O(1)。 但是这样跟纯嵌套循环没有什么区别，只是最后一层少了一个因子n。有什么办法能优化？
就是说，对于 k sum (k>2) 问题 （一个size为n的array, 查找k个数的一个tuple，满足总和sum为0）， 有没有时间复杂度在O(n^(k-2))的办法？
之前常规的一层一层剥离，n的次数是递增的。只有在最后一层，还有两个维度的时候，时间开销上减少一个n的因子，但是这样时间开销还是太多
我们可以通过对问题分解来解决
举个例子
...-5，-4，-3，-2，-1, 0，1, 2, 3, 4, 5.... 要找 4 sum = 0
那么先分解
4 分成 2 sum + 2 sum 来解决，但是这里的子问题2 sum没有sum=0的要求，是保留任何中间值。只有当子问题的2 sum解决以后，回归原问题的时候，我们才又回归原始的2 sum问题，这时候sum=0
子问题，空间和时间消耗，都是O(n^2)
回归大问题，时间消耗，是O(n^2)
假设k sum中 k = 2^m, 那么一共有m层，会有m次分解
分解到最底层，时间空间消耗 从 原始O(n)变为新的O(n^2)
分解到次底层，时间空间消耗 从 O(n^2)变为新的O((n^2)^2)
...
到达最顶层，时间空间消耗就都变成了O(n^(2*m)) = O(n^(2logk))
和之前的方法O(n^(k-1))相比，O(n^(2logk))的时间是少了很多，但是空间消耗却很大。
因为子问题无法确定把哪一个中间结果留下，那么就需要把子问题的结果全部返回，到最后，空间消耗就很大了。整体效果算是空间换时间吧。
通过 问题的分解 + hashtable的运用，能明显减少时间消耗， 但是空间消耗变大是个问题。比如说，如果有10^6的int类型数组，我如果用这个hashtable的办法，就要有10^12的pair，这就有10T以上的空间消耗。
问题的分解是个很好的思路，但是中间值得保留迫使空间消耗增大，这和用不用hashtable倒没有很大关系，只是说，如果不用hashtable，时间消耗会更大。
另外，还有一些题目的变形，比如如果要求所有组合，满足
sum < k,
sum = k,
sum > k,
或者是 closest to k
遇到这些变形的时候，hashtable的做法就显得乏力了，但是嵌套循环的方式却仍是可行的。尤其是对closest to k这种非确定性的要求。
No comments:
Post a Comment