剑指Offer（四十一）和为S的连续整数序列（Java版 )

﹏ヽ暗。殇╰゛Y 2021-09-27 00:08 183阅读 0赞

# 一、题目描述 #

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

# 二、题目分析 #

## Step1： ##

看下这个问题的简化版：  
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，任意输出一对。  
输入数组\{1，2，4，7，11，15\}和15，输出4，11

/* *
     * i,j分别表示数组两端下表
     * 当array[i]+array[j]>S时，j-- 尾端向前移动，两数据和增大
     * 当array[i]+array[j]=S时，将array[i],array[j]依次添加到ArrayList中
     * 当array[i]+array[j]<S时，i++前段向后移动，两数据和减小
     * */
    public class Test5 {
        public static void main(String[] args) {
            int[] array = {
       1,2,4,5,11,15};
            int sum = 15;
            ArrayList<Integer> list = new ArrayList<Integer>();
            if (array == null || array.length < 2) {
                System.out.print("2");
            }
            int i=0,j=array.length-1;
            while(i<j)
            {
                if(array[i]+array[j] == sum)
                {
                    list.add(array[i]);
                    list.add(array[j]);
                    break;
                }else if(array[i]+array[j]>sum){
                    j--;
                }else{
                    i++;
                }
            }
            System.out.println(list);
        }
    }

## Step2： ##

现在来分析下本题：  
双指针技术，就是相当于有一个窗口，窗口的左右两边就是两个指针，我们根据窗口内值之和来确定窗口的位置和宽度。非常牛逼的思路，虽然双指针或者所谓的滑动窗口技巧还是蛮常见的，但是这一题还真想不到这个思路。

import java.util.ArrayList;
    public class Solution {
        public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
            //存放结果
            ArrayList<ArrayList<Integer> > result = new ArrayList<>();
            //两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
            int plow = 1,phigh = 2;
            while(phigh > plow){
                //由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
                int cur = (phigh + plow) * (phigh - plow + 1) / 2;
                //相等，那么就将窗口范围的所有数添加进结果集
                if(cur == sum){
                    ArrayList<Integer> list = new ArrayList<>();
                    for(int i=plow;i<=phigh;i++){
                        list.add(i);
                    }
                    result.add(list);
                    plow++;
                //如果当前窗口内的值之和小于sum，那么右边窗口右移一下
                }else if(cur < sum){
                    phigh++;
                }else{
                //如果当前窗口内的值之和大于sum，那么左边窗口右移一下
                    plow++;
                }
            }
            return result;
        }
    }

运行结果：  
![这里写图片描述][70]

> **转载请标明出处，原文地址：[https://blog.csdn.net/weixin\_41835916][https_blog.csdn.net_weixin_41835916]  
> 如果觉得本文对您有帮助，请点击顶支持一下，您的支持是我写作最大的动力，谢谢。**

[70]: /images/20210923/8f29dffb6c3c4c38971b50333e9b7dc4.png
[https_blog.csdn.net_weixin_41835916]: https://blog.csdn.net/weixin_41835916