0

任务是找到所有连续子集，或者更好地说是具有特定总和的子数组，其中子集可以包含正整数和负整数示例：对于子集={1,-1,1,-1,1}，所有这些子集都会导致总和1个是：

{1}
{1,-1,1}
{1}
{1,-1,1,-1,1}
{1,-1,1}
{1}

这意味着有 6 个子集的总和为 1……我已经通过保存以前的总和来尝试过，但我仍然只能使用 2 个循环来做到这一点……一个从 0 到 n，另一个从 0 到 i-1 这里是代码：

  for (i = 0; i < n; i++)
  {
      scanf("%d", &a1[i]); 
      sum[i] = a1[i] + a1[i - 1];
  }

  sum[0] = INT_MAX;
  for (i = 0; i < n; i++)
  {
      if (a1[i] == 1 || a1[i] == -1)
      {
          count++;
      }

      if (i > 0)
      {
          if (sum[i] == 1 || sum[i] == -1)
          {
              count++;
          }

          for (j = 0; j < i - 1; j++)
          {
              if ((sum[i - 1 - j] + a1[i] == 1) || (sum[i - 1 - j] + a1[i]) == -1)
              {
                  count++;
              }

              sum[i - 1 - j] += a1[i];
          }
      }
  }

有没有办法在 O(n) 或 O(nlogn) 时间复杂度中做到这一点？

4

2 回答 2

1

不，没有办法，因为存在具有给定总和的 O(N^2) 个切片的 N 元素数组。仅枚举输出需要 O(N^2)。

示例：数组 { +1, -1, +1, -1 ... }（长度 N = 2k+1）与所需的总和 +1。

  • 有 N-2 个长度为 3 的切片加起来为 +1
  • 有 N-4 个长度为 5 的切片加起来为 +1
  • ... 有 3 个长度为 N-2 的切片加起来为 +1
  • 有 1 个长度为 N 的切片加起来为 +1

总计：1 + 3 + ... + N-2 = 2 * (1 + 2 + ... + k) - k = k^2

于 2013-09-12T16:34:17.430 回答
-1

由于我仍然无法对帖子发表评论...

我们是否应该假设总和为 +1，设置 {1, -1, 1} 和 {-1, 1, 1} 不同？

使用 3 个元素获得 +1 总和的唯一方法是组合 +1、+1 和 -1。

现在假设元素的顺序很重要，最多可以有 3 个！= 6 套，最多可以加起来 +1 。

如果 N = 2k+1，设 k = 100，N = 201，我仍然看不到 N-2 = 199 个长度为 3 且总和为 +1 的子集，除非 -1 在第二个位置并且 -1 是原始集合中的另一个位置被视为不同的-1

于 2013-09-12T16:56:28.163 回答