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
比如
Member discussion