对于暴力枚举的一些优化方法的题解

话不多说先上题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

举例：

输入：target = 9
输出：[[2,3,4],[4,5]]

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
接下来是分析题目：
这种题很简单 当然是为了作为例子来说明的啦 
题目我们要注意这几点：输出的大致上是一个二维数组，最里边的数组至少两个元素 并且是连续的 这提示给我们一个信息 如果暴力枚举 最终是停在target/2向下取整上
在程序里 我们用(target - 1) / 2 来表示 target / 2 下取整（纯粹的数学问题）
我们首先想到的方法肯定是暴力枚举 做是肯定好做 问题在一些细节以及简洁程度上 这里就给出暴力枚举比较简洁的代码：

 1 class Solution {
 2 public:
 3     vector<vector<int>> findContinuousSequence(int target) {
 4         vector<vector<int>> vec;
 5         vector<int> res;
 6         int sum = 0, limit = (target - 1) / 2; 
 7         for (int i = 1; i <= limit; ++i) {
 8             for (int j = i;; ++j) {
 9                 sum += j;
10                 if (sum > target) {
11                     sum = 0;
12                     break;
13                 }
14                 else if (sum == target) {
15                     res.clear();//清空数组
16                     for (int k = i; k <= j; ++k) res.emplace_back(k);//类似栈一样向容器后添加元素 
17                     vec.emplace_back(res);
18                     sum = 0;
19                     break;
20                 }
21             }
22         }
23         return vec;
24     }
25 };

对于这种算法 我们给出分析：
首先是时间复杂度 由于时间复杂度的性质 我们可以看出 
真正决定时间复杂度的无非就是

   for (int i = 1; i <= limit; ++i) {

   for (int j = i;; ++j) {

这两行 他们是外层循环和内层循环 时间复杂度要相乘的  而后边的操作都是常数级别的操作 或者说

 for (int k = i; k <= j; ++k) res.emplace_back(k);//类似栈一样向容器后添加元素

时间复杂度比它小或者同阶总之不比它大

所以我们只需要关注

  for (int i = 1; i <= limit; ++i) {
   for (int j = i;; ++j) {

这两个

因为 外层循环 最多到limit次 也就是(target - 1) / 2;时间复杂度O（n）
内层 如果是从1开始累加 最多也就是加到根号下target（这还是数学）时间复杂度O（根号n）
也就是最终的时间复杂度O（target√target）
对于空间复杂度
因为是用常数数组存放变量 所以是O（1）

接着我们对这种方法进行优化：

对于这种数组问题 还是连续的变量 是由起点到终点的一个遍历求和验证 用双指针（统称）会好很多  其实具体的称呼是“滑动窗口法”
所以我们可以用l和r（左边和右边）两个指针表示起点终点

sum 表示 [l,r] 的区间和，由求和公式可求得
sum= （l+r）（r-l+1）/2

之后一共有三种情况：

如果 sum<target 则说明指针 r 还可以向右拓展使得 sum增大，此时指针 r向右移动，即 r++
如果 sum>target则说明以 l 为起点不存在一个 r 使得 sum=target ，此时要枚举下一个起点，指针 l 向右移动，即l++
如果 sum==target 则说明我们找到了以 l 为起点得合法解 [l,r]，我们需要将 [l,r] 的序列放进答案数组，且我们知道以 l 为起点的合法解最多只有一个，所以需要枚举下一个起点，指针 l 向右移动，即 l++

终止条件也就是l>r，此时 r移动到了

(target - 1) / 2+1  l<r时区间和始终大于target
此方法其实是对方法一的优化，因为方法一是没有考虑区间与区间的信息可以复用，只是单纯的枚举起点
我们是利用了已知的信息来优化时间复杂度的 是考虑的实际情况 除非是sum不够大 我们才需要向右扩展 不然我们对于其他情况都是l++
代码如下

 1 class Solution {
 2 public:
 3     vector<vector<int>> findContinuousSequence(int target) {
 4         vector<vector<int>>vec;
 5         vector<int> res;
 6         for (int l = 1, r = 2; l < r;){
 7             int sum = (l + r) * (r - l + 1) / 2;
 8             if (sum == target){
 9                 res.clear();
10                 for (int i = l; i <= r; ++i) res.emplace_back(i);
11                 vec.emplace_back(res);
12                 l++;
13             }
14             else if (sum < target) r++;
15             else l++;
16         }
17         return vec;
18     }
19 };

而从另一个方面在数学的角度

既然是求和还是等差数列求和完全可以公式化化为一个函数表达式然后把一个np问题转化为p问题把时间复杂度化为常数阶

也就是是否存在一个正整数y（y>x)使得

也就是：

我们只需要求解这个一元二次方程就好（求根公式）

但是解必须是整数

也就是这两个条件

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> vec;
        vector<int> res;
        int sum = 0, limit = (target - 1) / 2; // (target - 1) / 2 等效于 target / 2 下取整
        for (int x = 1; x <= limit; ++x) {
            long long delta = 1 - 4 * (x - 1ll * x * x - 2 * target);
            if (delta < 0) continue;
            int delta_sqrt = (int)sqrt(delta + 0.5);
            if (1ll * delta_sqrt * delta_sqrt == delta && (delta_sqrt - 1) % 2 == 0){
                int y = (-1 + delta_sqrt) / 2; // 另一个解(-1-delta_sqrt)/2必然小于0，不用考虑
                if (x < y) {
                    res.clear();
                    for (int i = x; i <= y; ++i) res.emplace_back(i);
                    vec.emplace_back(res);
                }
            }
        }
        return vec;
    }
};

时间复杂度仅仅为枚举开头（到target-1/2）

也就是O（target）

空间复杂度为O（1）