[剑指Offer]-和为S的连续正数序列

95 阅读 0 评论 63 点赞

我是靠谱客的博主妩媚灯泡，这篇文章主要介绍[剑指Offer]-和为S的连续正数序列，现在分享给大家，希望可以做个参考。

题目描述

输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1-5,，4-6和7-8.

解题思路

以求和为9的所有连续序列为例，假设两个指针pSmall和pBig
一开始pSmall=1，pBig=2，，pSum=3<9，序列需要包含更多的数，于是pBig+1，
此时pSum=6，依旧小于9，于是pBig+1，此时pSum=10，大于9，序列需要删除一些数，
于是pSmall-1，pSum=9，找到第一个满足条件的序列；接着pBig+1，
按照前面的方法继续查找满足条件的序列，直到pSmall等于(s+1)/2.

算法图解

在这里插入图片描述

参考代码：

复制代码

package offer;

/**
 * 和为s的连续正数序列
 * 输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1-5,，4-6和7-8.
 */
public class Offer57_2 {
    public static void main(String[] args) {
        int nums[] = {1, 2, 3, 4, 5, 6, 7, 8};
        findContinuous(nums, 15);
    }

static void findContinuous(int nums[], int s) {
        if (nums == null || s <= 0 || nums.length < 1) {
            return;
        }
        int small = 1;
        int big = 2;
        int currsum = 3;
        int mid = (1 + s) / 2;
        while (small < mid) {
            if (currsum == s) {
                for (int i = small; i <= big; i++) {
                    System.out.print(i);
                }
                System.out.println();
            }
            while (currsum > s && small < mid) {
                currsum -= small;
                small++;
                if (currsum == s) {
                    for (int i = small; i <= big; i++) {
                        System.out.print(i);
                    }
                    System.out.println();
                }
            }
            big++;
            currsum += big;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package offer;

/**
 * 和为s的连续正数序列
 * 输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1-5,，4-6和7-8.
 */
public class Offer57_2 {
    public static void main(String[] args) {
        int nums[] = {1, 2, 3, 4, 5, 6, 7, 8};
        findContinuous(nums, 15);
    }

    static void findContinuous(int nums[], int s) {
        if (nums == null || s <= 0 || nums.length < 1) {
            return;
        }
        int small = 1;
        int big = 2;
        int currsum = 3;
        int mid = (1 + s) / 2;
        while (small < mid) {
            if (currsum == s) {
                for (int i = small; i <= big; i++) {
                    System.out.print(i);
                }
                System.out.println();
            }
            while (currsum > s && small < mid) {
                currsum -= small;
                small++;
                if (currsum == s) {
                    for (int i = small; i <= big; i++) {
                        System.out.print(i);
                    }
                    System.out.println();
                }
            }
            big++;
            currsum += big;
        }
    }
}