每日算法之和为S的连续正数序列
JZ74 和为S的连续正数序列题目
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。
现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?方法1 枚举法
思路
算法实现
从数字1开始枚举连续的数字，将其累加判断其是否等于目标，
如果小于目标数则继续往后累加，
如果大于目标数说明会超过，跳出，
继续枚举下一个数字开始的情况（比如2，比如3），
这样每次都取连续的序列，只有刚好累加和等于目标数才可以记录从开始到结束这一串数字，代表是一个符合的序列。
具体做法：
step 1：从1到目标值一半向下取整作为枚举的左区间，即每次序列开始的位置。
step 2：从每个区间首部开始，依次往后累加，如果大于目标值说明这一串序列找不到，换下一个起点。
step 3：如果加到某个数字刚好等于目标值，则记录从区间首到区间尾的数字。代码
package mid.JZ74和为S的连续正数序列;import java.util.ArrayList;public class Solution { /** * 枚举法 * @param sum * @return */ public ArrayList FindContinuousSequence(int sum) { ArrayList res = new ArrayList(); if (sum == 0) return new ArrayList(); //因为序列至少两个数，因此枚举最多到该数字的一半向下取整 int sum1 = 0; int mid = (sum - 1) / 2; for (int i = 1; isum) { sum1 = 0; break; } else if (sum1 == sum) { ArrayList temp = new ArrayList(); for (int k = i; k
页:
[1]