A18 双指针 尺取法

题目情境#

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

题目描述

给定一个正整数 $M$，求出所有的连续的正整数段（每一段至少有两个数），使得这些连续的正整数段中的全部数之和为 $M$。

例如，$1998+1999+2000+2001+2002=10000$，所以从 $1998$ 到 $2002$ 的一个正整数段为 $M=10000$ 的一个解。

输入格式

输入一行一个正整数，表示 $M$ 的值（$10\le M\le 2\times 10^6$）。

输出格式

输出每行包含两个正整数，表示一个满足条件的连续正整数段的左右端点，两数之间用一个空格隔开。

输出按左端点大小升序排列。

输入输出样例

输入 #1

10000

输出 #1

18 142 
297 328 
388 412 
1998 2002

说明/提示

对于 $100\%$ 的数据，保证至少有一个解。

算法解析#

本题可以使用双指针尺取法求解，维护一个左端点 $i$ 和右端点 $j$，并维护当前区间和 $sum=i+(i+1)+\cdots+j$。

• 初始令 $i=1,j=1,sum=1$。
• 若 $sum < M$，则右指针右移：$j\leftarrow j+1$，并把新的值加到 $sum$ 中。
• 若 $sum > M$，则左指针右移：把 $i$ 从 $sum$ 中减去，$i\leftarrow i+1$。
• 若 $sum = M$，则记录当前区间 $[i,j]$，再移动左指针继续搜索。

由于每个指针最多右移 $O(n)$ 次，整体时间复杂度为 $O(n)$。

Python代码实现#

m = int(input())
i = 1
j = 1
sum = 1
while i <= m // 2:
    if sum < m:
        j += 1
        sum += j
    if sum >= m:
        if sum == m:
            print(i, j)
        sum -= i
        i += 1

C++代码实现#

#include<cstdio>

int main(){
  int m; scanf("%d",&m);
  int i=1,j=1,sum=1;
  while(i<=m/2){      //i<=j
    if(sum<m){
      j++;
      sum+=j;
    }
    if(sum>=m){
      if(sum==m) printf("%d %d\n",i,j);
      sum-=i;
      i++;
    }
  }
  return 0;
}