《剑指offer》—— 41. 和为S的连续正数序列（Java）
推荐
完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述：
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
}
}
思路：
滑动窗口（双指针）
根据窗口内的值来移动窗口。
简单来说就是：
一个指针指着低位，一个指针指着高位。
如果两个指针之间的序列和小于目标值，则右指针后移一位；
如果两个指针之间的序列和大于目标值，则左指针后移一位；
示例: 找出和为9的整数序列
- 一个低位指针指着1，一个高位指针指着2： →1 → 2 3 4 5 6 7 8 ……
1~2及之间的和为3，小于9 - 高位指针后移 ：→1 2 →3 4 5 6 7 8 ……
1~3及之间的和为6，小于9 - 高位指针后移 ：→1 2 3 →4 5 6 7 8 ……
1~4及之间的和为 10 ，大于9 - 低位位指针后移 ：1 →2 3 →4 5 6 7 8 ……
2~4及之间的和为9 ，等于9。找到一个满足要求的序列，记录下来，然后将高位后移并继续操作。 - 高位指针后移 ：1 →2 3 4 →5 6 7 8 ……
2~5及之间的和为14 大于9 - 低位指针后移 ：1 2 →3 4 →5 6 7 8 ……
3~5及之间的和为12 大于9 - 低位指针后移 ：1 2 3 →4 →5 6 7 8 ……
4~5及之间的和为9 大于9。找到一个满足要求的序列，记录下来，然后将高位后移并继续操作。 - 高位指针后移 ：1 2 3 →4 5 →6 7 8 ……
4~6及之间的和为15 大于9。 - 低位指针后移 ：1 2 3 4 →5 →6 7 8 ……
5~6及之间的和为11，大于9。 - 低位指针后移 ：1 2 3 4 5 → →6 7 8 ……
两个指针相遇，后面不可能再会有序列和等于目标值。停止判断。输出最终结果。
注意: 其实找到一个满足要求的序列之后，让低位后移更好，因为最后可以少判断。
实现：
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
//存储最终结果的数组
ArrayList<ArrayList<Integer> > result = new ArrayList<>();
//低位指针
int pLow = 1;
高位指针
int pHigh = 2;
while(pLow < pHigh){
//pLow 到 pHigh 连续序列值的和
int order = (pLow + pHigh) * (pHigh - pLow + 1) / 2;
if (order == sum) {
ArrayList<Integer> list = new ArrayList<>();
for (int i = pLow; i <= pHigh; i++){
list.add(i);
}
result.add(list);
pLow++;
} else if (order > sum){
pLow++;
} else {
pHigh++;
}
}
return result;
}
}
看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。
这里是猿兄，为你分享程序员的世界。
非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！
注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！
比亚迪成长空间 160人发布