题解 | #和为S的连续正数序列#

牛客-JZ41题解

题目分析

题目标签🏷️：数组，数学公式，滑动窗口，双指针

初看，这道题是要求我们在一个无穷整数序列中找出所有的连续正整数数组arr使得数组中元素的和恰好位S。

看起来很麻烦，因为连续正整数数组有无穷多个，那么如何在这无穷多个数组中选择找出目标数组呢？

首先，我们需要从题目当中给出的条件来简化问题，缩小搜索范围，看看题目中都有什么条件可以利用（已经用方框标注好了）：

• 连续正序列

​ 这就要求目标数组中最后一个元素的值不可能大于S

• 至少两个数

​ 要保证有至少两个连续数，那么目标子数组中元素的值不可能都大于S/2，所以，搜索的右边界可以界定下来了，它是S/2；

现在，再看看经过简化后的问题：

找出1，2，…，S/2序列中，满足以下条件的连续子数组：1）元素个数大于2；2）连续子序列元素的和为S。

解法

下面，我们来看看解题法。

1原始版：

最原始的方法，我们便利1,2…,S/2序列，分别找出

• 以1开头且和为S的连续子序列
• 以2开头且和为S的连续子序列
• ...
• 以S/2-1开头的和为S的连续子序列

我们需要两轮循环，外循环界定子序列起始位置点，内循环界定子序列终止位置点，因为总的时间复杂度是O(n^2)，空间复杂度为O(1)。

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        if(sum <= 0) return res;
        int n = (sum + 1) / 2;
        vector<int> tmp;
        for(int i = 1; i < n; i++) {
            int curSum = i;
            tmp.clear();
            tmp.push_back(i);
            for(int j = i + 1; j <= n; j++) {
                curSum += j;
                tmp.push_back(j);
                if(curSum == sum) {
                    res.push_back(tmp);
                    continue;
                }
            }
        }
        return res;
    }
};

PASS:

作为一个对性能有要求的人，肯定不能止步于此。我们仔细分析下刚才的程序，针对外循环中每一次遍历，我们都是从头开始计算，并没有利用上一次计算的结果信息，导致很多冗余计算。因此，我们要想办法减少这些冗余计算。

现在的问题是，如何利用上一次计算的信息，来加速本轮子数组和的计算。

2 进阶版

每一轮外循环中，是否一定要进行内循环的计算呢？

我们固定住了a0, 其实就是找a0为第一项，等差为1，和为sum的等差数列，未知变量就只剩这个等差子序列的项数n了。根据等差数列求和公式：

我们得到方程：

根据方程通用公式，得到关于n的方程的解：

其中，n需要为整数。

因此，每一轮外循环，我们都要求n，然后通过判断n是否为整数，来判断这一轮外循环是否有满足的子数组存在。

class Solution {
public:
      vector<vector<int>> FindContinuousSequence(int sum) {
          vector<vector<int>> res;
          if(sum <= 0) return res;
          int n = (sum + 1) / 2;
          // 公式：n^2 - (2 * arr0 - 1)^2 * n - 2 * S = 0
          // 方程的解：n = (sqrt((2*arr0 - 1)^2 + 8*S) - 1)/ 2
          for(int i = 1; i < n; i++) {
              int m = (2 * i - 1) * (2 * i - 1) + 8 * sum;
              int t = sqrt(m);
              if(t * t == m && ((m - 1) % 2 ==0)) {
                  int j = (t - 1) / 2;
                  vector<int> tmp(j - i + 1);
                  for(int k = 0;k <= tmp.size(); k++) tmp[k] = i+k;
                  res.push_back(tmp);
              }
          }
          return res;
      }
};

PASS:

3 滑动窗口

本题属于连续子序列和，碰到这类题一个比较通用有效的计算方法是双指针形成滑动窗口，通过左右指针l和r之间的和和目标sum的比较结果来决定下一步是扩展窗口还是缩小窗口。

这其实是方法二思路是一致的，区别是在循环中判断某一个一个字数组是否满足条件：

• 方法二通过固定子数组和sum， 第一项arr0，从而求元素个数n，并通过n是否为整数来判断该子数组是否满足条件；
• 方法三是直接在遍历过程中求子数组和S，然后判断S和目标sum是否相等作为判断条件；

​ 方法三的遍历也不同，通过每一步根S比较来前进。

class Solution {
public:
      vector<vector<int>> FindContinuousSequence(int sum) {
          vector<vector<int>> res;
          if(sum <= 0) return res;
          int n = (sum + 1) / 2;
          int l = 1, r = l + 1;
          int curSum = 0;
          vector<int> vec;
          while(r - l >= 1 && r <= n) {
              curSum = (r + l) * (r - l + 1) / 2;
              if(curSum == sum) {
                  for(int i = l; i <= r; i++) vec.push_back(i);
                  res.push_back(vec);
                  vec.clear();
                  l++;
              }
              else if(curSum < sum) {
                  r++;
              }
              else{
                  l++;
              }
          }
          return res;
      }
};

PASS:

思考：

思考下，方法二和方法三相比于方法二优化在什么地方呢？

对比可以看到，外循环是一致的，差别在内循环上。

• 在方法一中，针对每一轮的外循环，都会有一轮内循环计算，因此时间复杂度是O(n^2);
• 在方法二和三种，我们在外循环种增加了条件判断，只有当自数组的和满足条件时，才会进行内循环的计算，这个内循环的计算在方法二和三中的目的只是将找到的子数组元素组织起来，然后放到返回结果数组中。

【注意】：

在分析时间和空间复杂度上，由于牛客的测试用例和计算方式问题，运行时间一般不能真实地反映真实的时间复杂度和空间复杂度，所以不要用PASS时的运行时间来比较算法的时间和空间复杂度。

最好是自己通过代码做分析和估算，得处结论。