知识点 穷举
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?
数据范围:0 < n< 100
进阶:时间复杂度 O(n)
返回值描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序.
求某个连续序列,很容易想到可以使用两个指针,一个指向序列头,一个指向序列尾。两个指针区间内的值的相加和语给定值比较。整个数组其实就是从1~n的正数组成所有数(想象有这么一个数组,不用真的去创建这么一个数组)。
假设传入的值为sum, 使用ArrayList
1、头、尾指针最开始都执行数组第一和第二个数据,即head=1, tail=2。用一个变量add来保存head~tail序列范围内数字相加和,所以初始add=head + tail = 3。还有为了保存所有满足条件的序列,使用一个列表ArrayList
sublist变量来保存head~tail区间内的数字。 2、开启循环,循环条件是head<=sum && tail < sum && head < tail,
3、比较add和sum值,
如果add = sum,则当前head~tail区间的序列满足条件。创建一个新的ArrayList
temp来存放这个序列区间的值,然后把list.add(temp)。然后让add变小,则把sublist中的head从列表中移除,然后add = add - head。再把head往后移动一步,即head++。进入下一次循环; 如果add < sum,需要让add变大,则往后移动tail一步,即add++,并且存入sublist中,再调整add = add + tail。进入下一次循环;
如果add > sum,需要让add变小,则把sublist中的head从列表中移除,然后add = add - head。再把head往后移动一步,即head++。进入下一次循环;
4、循环结束后,list就是我们想要的结果啦。
有几点需要注意下,当找到目标序列后,需要创建一个新的ArrayList
算法中还使用了变量add动态地求出了head~tail区间内的数据和,这点还蛮好的。
代码实现如下:
- import java.util.ArrayList;
- public class Solution {
- public ArrayList
> FindContinuousSequence(int sum) { - //用两个指针来遍历数组,两个指针区间的数字和等于目标值,则存入目标列表中
- ArrayList
> list = new ArrayList >(); - int before = 1;
- int after =2;
- int add = 3;
- ArrayList
subList = new ArrayList(); - subList.add(1);
- subList.add(2);
- while (before <= sum/2 && before < after && after < sum) {
- if (add == sum) {
- ArrayList
tempList = new ArrayList(); //创建一个为空临时列表来存储符合条件的数据集合 - tempList.addAll(subList);
- list.add(tempList);
- if (subList.size() >=1) {
- subList.remove(0);
- }
- add = add - before;
- //搞了半天一直调试不通过是因为这里写错了,这种写法会导致before变量在循环过程中保持不变
- //before = before++;
- before++;
- } else if (add > sum) {
- if (subList.size() >=1) {
- subList.remove(0);
- }
- add = add - before;
- //搞了半天一直调试不通过是因为这里写错了,这种写法会导致before变量在循环过程中保持不变
- //before = before++;
- before++;
- } else {
- after++;
- subList.add(after);
- add = add + after;
- }
- }
- return list;
- }
- }
还有一点特别强调下:在调试的时候一直报错,但是检查逻辑没发现什么问题。后来通过打断点调试,发现代码中的before变量在循环过程中一直保持为1,没有变化。这个很奇怪。
刚开始使用的是before = before++; 罪魁祸首就是这里了,这种写法会导致before永远不变(具体原因参考文章:"Java中关于a=a++结果的解释"和“a=a++理解”)。把before = before++;替换成before++;,运行后正常了!!
最后,关于这道算法题,网上给出了好几种解法,可以参考和为S的连续正数序列_楚楚可薇的博客-CSDN博客_和为s的连续正数序列