和为S的连续正数序列-白红宇

和为S的连续正数序列

阅读量：3964 次

发布时间：2019-05-24

本文共 1760 字，大约阅读时间需要 5 分钟。

##题目描述小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。

思路

题目意思是求一组公差为1和为sum的等差数列。

方法1（推荐）：
快慢指针滑动窗口。
设置两个指针指向等差数列左右两端，利用等差数列求和公式验证。
右指针右移一步，相当于拿一个未使用的最小值进来，
左指针左移一步，相当于拿一个已使用的最小值出去。
时间复杂度O(n)，空间复杂度O(1)。

方法2:
等差数列求和。
在本题场景中，符合条件的等差数列的长度上限，是从1开始的数列的长度。
可能符合条件的最长的等差数列和为n(n+1)/2，此时，d = 1， a1 = 1。
根据不等式 Sn = n(n+1)/2，可以求解出 n <= √（2Sn）。
得到数列长度n的取值范围后，可以直接使用Sn除以n得到数列的平均数，从而求出数列。
当n为奇数时，求得的正好是等差数列中间的值。
当n为偶数时，求得的是均值，该均值小数部分是0.5，即Sn%n=n/2 => Sn%n*2=n。
时间复杂度O(√n)，空间复杂度O(1)。

滑动窗口代码（算法思维容易接受）

import java.util.ArrayList;public class Solution {    public ArrayList
   
    
      > FindContinuousSequence(int sum) {        ArrayList
     
      
       > list = new ArrayList
       
        
         >(); if(sum < 3) return list; int low = 1; int high = 2; int curr = 3; // 判断条件不能包含等于，至少需要包含两个数字，所以low最大只能到high-1。 while(low < high) { curr = (low + high) * (high - low + 1)/2; if(curr == sum) { ArrayList
         
           item = new ArrayList
          
           (); for(int i = low; i <= high; i++) { item.add(i); } list.add(item); high++; } else if(curr < sum) { high++; } else { low++; } } return list; }}

数学方法代码（需要分析推导）

import java.util.ArrayList;public class Solution {    public ArrayList
   
    
      > FindContinuousSequence(int sum) {        ArrayList
     
      
       > list = new ArrayList
       
        
         >(); if(sum < 3) return list; for(int len = (int)Math.sqrt(2*sum); len > 1; len--) { if((len&1) == 1 && sum % len == 0 || sum % len * 2 == len) { int k = sum / len - (len - 1) / 2;; ArrayList
         
           item = new ArrayList
          
           (); for(int i = 0; i < len; i++) { item.add(k++); } list.add(item); } } return list; }}

转载地址：http://dfuki.baihongyu.com/

你可能感兴趣的文章