剑指offer-41、和为S的连续正数序列
<h2 id="题描述">题⽬描述</h2><p>⼩明很喜欢数学，有⼀天他在做数学作业时，要求计算出 9~16 的和，他⻢上就写出了正确答案是 100 。但是他并不满⾜于此，他在想究竟有多少种连续的正数序列的和为 100 (⾄少包括两个数)。没多久，他就得到另⼀组连续正数和为 100 的序列: 18,19,20,21,22 。现在把问题交给你，你能不能也很快的找出所有和为S的连续正数序列? Good Luck!</p>
<p>返回值描述：输出所有和为 S 的连续正数序列。序列内按照从⼩⾄⼤的顺序，序列间按照开始数字从⼩到⼤的顺序</p>
<p>示例1：</p>
<p>输⼊：9<br>
返回值：[,]</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力枚举">暴力枚举</h3>
<p>通过双重循环尝试所有可能的序列起点和终点。</p>
<p>针对每⼀个索引起点，都计算后续的连续⼦数组的和，并且将元素存到临时 list 中。</p>
<p>如果和不超过 sum ,那么就继续往后⾯遍历；</p>
<p>如果和等于 sum ，则说明该连续⼦数组满⾜条件，将临时 list 添加到结果集中</p>
<p>如果和⼤于 sum ，则说明连续⼦数组已经超过，该索引起点的不满⾜条件，直接 break 。</p>
<p>注意的是，起点我们只需要遍历到 sum/2 的位置即可，因为⼤于 sum/2 的索引，任何两个数的和都⼤于 sum ，不符合条件。</p>
<pre><code class="language-java">import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (sum < 3) return result; // 至少需要两个数，最小和为1+2=3
// 序列起点最多到sum/2，因为至少两个数，第二个数肯定比sum/2大
for (int i = 1; i <= sum / 2; i++) {
int currentSum = 0;
ArrayList<Integer> sequence = new ArrayList<>();
// 从i开始累加，直到和大于等于sum
for (int j = i; j < sum; j++) {
currentSum += j;
sequence.add(j);
if (currentSum == sum) {
result.add(new ArrayList<>(sequence)); // 找到有效序列
break;
} else if (currentSum > sum) {
break; // 已经超过，无需继续
}
}
}
return result;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n²)</li>
<li>空间复杂度：O(k)，k为结果序列数</li>
</ul>
<h3 id="数学计算">数学计算</h3>
<p>利用等差数列求和公式进行数学优化，减少计算量。</p>
<p>思路：设序列长度为n，起始为x，则满足：n*(2x+n-1)/2 = sum</p>
<pre><code class="language-java">import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (sum < 3) return result;
// 序列长度n从2开始尝试（至少两个数）
for (int n = 2; n * (n + 1) / 2 <= sum; n++) {
// 根据求和公式推导：sum = n*(2x+n-1)/2
// 解得：x = (2*sum/n - n + 1)/2
int numerator = 2 * sum - n * (n - 1);
int denominator = 2 * n;
// x必须是正整数，且分子要能整除分母
if (numerator > 0 && numerator % denominator == 0) {
int x = numerator / denominator;
ArrayList<Integer> sequence = new ArrayList<>();
for (int i = 0; i < n; i++) {
sequence.add(x + i);
}
result.add(sequence);
}
}
// 由于我们从长度小的开始，需要反转结果保证序列间顺序
result.sort((a, b) -> a.get(0) - b.get(0));
return result;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n)</li>
<li>空间复杂度：O(1)</li>
</ul>
<h3 id="滑动窗口最优">滑动窗口（最优）</h3>
<p>使用双指针技术，动态调整窗口大小</p>
<pre><code class="language-java">import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (sum < 3) return result;
int left = 1; // 窗口左边界
int right = 2; // 窗口右边界
int currentSum = left + right; // 当前窗口和
// 左边界最多到sum/2，因为至少需要两个数
while (left <= sum / 2) {
if (currentSum == sum) {
// 找到有效序列，添加到结果
ArrayList<Integer> sequence = new ArrayList<>();
for (int i = left; i <= right; i++) {
sequence.add(i);
}
result.add(sequence);
// 左边界右移，继续寻找
currentSum -= left;
left++;
} else if (currentSum < sum) {
// 和太小，扩大窗口（右边界右移）
right++;
currentSum += right;
} else {
// 和太大，缩小窗口（左边界右移）
currentSum -= left;
left++;
}
}
return result;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(n）</li>
<li>空间复杂度：O(1)</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19256937
頁:
[1]