LeetCode 面试题57 - II. 和为s的连续正数序列

段连洁 -

面试题57 - II. 和为s的连续正数序列

Difficulty: 简单

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

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

示例 1：

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

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

  • 1 <= target <= 10^5

解法

暴力法 嵌套 两个for 循环 (也可以是while 循环), 将起点一点一点累加

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        if (target == 1) return {};
        // 暴力 n^2
        vector<vector<int>> ans;
        int end = (target) / 2 + 1;
        int begin = 1;
        while (begin <= end) {
            int cur = begin;
            while (cur <= end) {
                int sum = (cur + begin) * 0.5 * (cur-begin+1);
                if (sum == target && cur > begin) {
                    vector<int> s;
                    for (int i = begin;i<=cur;i++) {
                        s.emplace_back(i);
                    }
                    ans.emplace_back(s);
                    break;
                } else if (sum > target) {
                    break;
                }
                cur++;
            }
            begin++;
        }
        return ans;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了54.51%的用户
内存消耗 :9.2 MB, 在所有 C++ 提交中击败了100.00%的用户

最开始我的暴力提交, 效率只超过了20%多
原因① 计算 sum 的时候是累计的, 没想到用高斯求和公式,当然这不是主要原因.但更易读
原因② 使用了 push_back 而不是 emplace_back , 就这一个改变,让时间从 12ms 优化到了 8ms , 击败率 从 27.79% 上升到 54.51%. 只能说对于这个语法是服了.

The following code uses emplace_back to append an object of type President to a std::vector. It demonstrates how emplace_back forwards parameters to the President constructor and shows how using emplace_back avoids the extra copy or move operation required when using push_back.
emplace_back 避免了额外的复制和移动操作, 减少了临时变量的产生 优化了效率
摘自 https://en.cppreference.com/w/cpp/container/vector/emplace_back

其实双指针更优雅的解法是下面的滑动窗口, 可读性比上面的高很多.
滑动窗口

数组就是正整数序列[1,2,3,…,n]。我们设滑动窗口的左边界为 i，右边界为 j，则滑动窗口框起来的是一个左闭右开区间 [i,j)。注意，为了编程的方便，滑动窗口一般表示成一个左闭右开区间。在一开始，i=1,j=1，滑动窗口位于序列的最左侧，窗口大小为零。
滑动窗口的重要性质是：窗口的左边界和右边界永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n), 如果左右边界向左移动的话，这叫做“回溯”，算法的时间复杂度就可能不止O(n)
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/shi-yao-shi-hua-dong-chuang-kou-yi-ji-ru-he-yong-h/

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        if (target == 1) return {};
        // 暴力 n^2
        vector<vector<int>> ans;
        // int limit = (target - 1) / 2;
        // for 循环的 新奇的写法 , 以前不会写for 循环啊
        // 双指针 也就是 滑动窗口
        for (int l = 1, r = 2;l<r;) {
            // 不需要累计, 直接利用高斯定理
            int sum = (l+r) * 0.5 * (r+1-l);
            if (sum == target) {
                vector<int> s;
                for (int i = l;i<=r;i++) {
                    s.emplace_back(i);
                }
                ans.emplace_back(s);
                l++;
            } else if (sum > target) {
                l++;
            } else {
                r++;
            }
        }
        return ans;
    }
};

执行用时 :8 ms, 在所有 C++ 提交中击败了54.51%的用户
内存消耗 :9.1 MB, 在所有 C++ 提交中击败了100.00%的用户

其他解法有利用等差数列,求根法
还有利用左右边界的间隔法, 优化取值次数等, 纯数学思想太厉害了.

TODO

更新滑动窗口的相关题目 LeetCode sliding-window

比如

参考