2

我有一个问题，它是子集和问题的一个非常明显的例子：

“给定 [-65000,65000] 范围内的整数列表，如果列表的任何子集求和为零，则函数返回 true。否则返回 false。”

我想问的是更多的解释而不是解决方案。

这是我在考虑问题的复杂性之前提出的一个特定于实例的解决方案。

  • 对数组 A[] 进行排序，并在排序期间将每个元素与计数器 'extSum' (O(NLogN)) 相加
  • 定义指针 low = A[0] 和 high = A[n-1]
  • 这是决定代码：
  • while(A[low]<0){
  sum = extSum;
  if(extSum>0){
    while(sum - A[high] < sum){
        tmp = sum - A[high];
        if(tmp==0) return true;
        else if(tmp > 0){
            sum = tmp;
            high--;
        }
        else{
            high--;
        }
    }
    extSum -= A[low];
    low++;
    high = n - 1;
  }
  else{
    /* Symmetric code: switch low, high and the operation > and < */
  }
}
return false;

首先，这个解决方案是否正确？我做了一些测试，但我不确定......看起来太容易了......
这段代码的时间复杂度不是O（n ^ 2）吗？

我已经阅读了各种 DP 解决方案，我想了解的是，对于我面临的问题的具体实例，它们比这种天真的和直观的解决方案要好得多。我知道我的方法可以改进很多，但在时间复杂度方面没有什么大不了的......

谢谢你的澄清

编辑：一个明显的优化是，在排序时，如果找到 0，函数会立即返回 true ......但这仅适用于数组中有 0 的特定情况。

4

1 回答 1

-1

嗯，我认为 {0} 会击败你的答案。

因为它会简单地忽略 while 并返回 false。

于 2011-09-15T16:51:21.017 回答