c - 查找具有特定总和(+ve 或 -ve)的所有连续子集，其中子集可以包含正整数和负整数

Question

任务是找到所有连续子集，或者更好地说具有特定总和的子数组，其中子集可以包含正整数和负整数例子:对于子集={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) 时间复杂度内做到这一点？

Answer 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