P1147 连续自然数和

题目描述

对一个给定的自然数M，求出所有的连续的自然数段，这些连续的自然数段中的全部数之和为M。

例子：1998+1999+2000+2001+2002 = 10000所以从1998到2002的一个自然数段为M=10000的一个解。

输入格式

包含一个整数的单独一行给出M的值（10≤M≤2,000,000）。

输出格式

每行两个自然数，给出一个满足条件的连续自然数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。

输入输出样例

===============================================================================

这道题目似乎用数学稍微推断一下就很容易得出答案^_^

我在解这道题目的时候，没有过多的利用数学公式去推断（等差数列求和），而是利用了双指针的解法：

左指针left肯定是从1开始（从0开始除了10以外好像别无意义），而且left其实无需到m，因为连续的自然数，必须要两个或以上才能称之为连续，而右指针是要比左指针要大的，所以左指针最多为m/2；

右指针的范围其实不需多做处理，因为如果和已经大于m的话，直接跳出右指针的循环即可

直接上代码：

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        for (int left = 1; left <= m / 2; left++){
            int sum = left;
            for (int right = left + 1; right <= m ; right++){
                sum += right;
                //当找到一个解时，打印出来之后可以直接退出本次循环了，因为越往后sum越大，在左指针固定的情况下不可能再有另一个解
                if (sum == m){
                    System.out.println(left + " " + right);
                    break;
                }
                //当前sum如果已经超过了m，直接跳出，无须再往下遍历
                if (sum > m)
                    break;
            }
        }
    }
}

这道题目还是比较简单的，不过用来练一下双指针倒是不错^_^

题目链接：https://www.luogu.com.cn/problem/P1147