剑指offer—和为S的连续正数序列 解答

剑指offer—和为S的连续正数序列

题目描述

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

思路

首先我们都可以想到使用多次循环遍历,但是时间复杂度太高,直接pass

我们想到和为sum的连续序列一定在1-(sum/2)中,减小了迭代的次数

  1. 我们怎么用一次遍历获取多个序列呢:

    答:双指针

    我们可以利用前后双指针来保存序列始末位置,当序列满足条件时把其中的元素全部添加到集合中

  2. 如何判断满足序列条件呢?(和为S)

    答:滑动窗口

    我们用双指针内的元素作为窗口,窗口中和小于sum时,右指针右移一位;大于sum时,左指针右移一位;相等时,添加到集合中

流程:

代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(sum<=1) return list;
        int l = 1,r = 1;
        while(r<=(sum/2)+1){
            int re = (l+r)*(r-l+1)/2;//序列求和公式
            if(re<sum) r++;
            else if(re>sum) l++;
            else{
                ArrayList<Integer> num = new ArrayList<>();
                for(int m=l;m<=r;m++){
                    num.add(m);
                }
                list.add(num);
                l++;r++;
            }
        }
        return list;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/sequence-num-s.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!