🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

整数的连续自然数之和表示(100分)

🌍 评测功能需要 订阅专栏 后私信联系清隆解锁～

🍓OJ题目截图

🍰 整数的连续自然数之和表示

问题描述

给定一个正整数 $T$，请找出所有用连续自然数之和来表示 $T$ 的方案。例如，整数 $9$ 可以表示为：$9=9$，$9=4+5$，$9=2+3+4$。你的任务是按照以下要求，输出所有表示 $T$ 的方案：

1. 优先输出自然数个数最少的表达式。
2. 每个表达式中的自然数按照递增顺序输出。
3. 最后输出表达式的总数。

输入格式

输入一个正整数 $T$。

输出格式

按照题目要求，输出所有表示 $T$ 的方案，每个方案占一行。最后一行输出 Result:X，其中 $X$ 表示方案总数。

样例输入1

9

样例输出1

9=9
9=4+5
9=2+3+4
Result:3

样例输入2

10

样例输出2

10=10
10=1+2+3+4
Result:2

数据范围

$1\le T\le 1000$

题解

本题可以使用双指针滑动窗口的思路来解决。我们可以用两个指针 $l$ 和 $r$ 分别表示当前连续自然数区间的左右端点，用变量 $total$ 维护区间 $[l,r]$ 内所有数的和。

初始时，$l=0$，$r=1$，$total=arr[l]$，其中 $arr$ 是从 $1$ 到 $T$ 的所有自然数组成的数组。

接下来，我们不断移动指针 $r$，并更新 $total$ 的值，直到 $total\ge T$。此时，如果 $total=T$，说明我们找到了一个合法的表达式，将 $arr[l,r]$ 加入答案数组中。然后我们将 $l$ 右移一位，并相应地减少 $total$ 的值，继续寻找下一个表达式。

当 $l$ 超过 $T$ 时，搜索结束。最后，我们将答案数组按照自然数个数从小到大排序，并按要求输出每个表达式即可。

时间复杂度 $O(T^2)$，空间复杂度 $O(T)$。

参考代码

• Python

t = int(input())

def getResult():
    arr = [i + 1 for i in range(t)]
    
    ans = []
    
    l, r, total = 0, 1, arr[0]
    
    while l < t:
        if total > t:
            total -= arr[l]
            l += 1
        elif total == t:
            ans.append(arr[l:r])
            total -= arr[l]
            l += 1
            if r >= t:
                break
            else:
                total += arr[r]
                r += 1
        else:
            total += arr[r]
            r += 1
    
    ans.sort(key=lambda x: len(x))
    
    for an in ans:
        print(f"{t}={'+'.join(map(str, an))}")
    
    print(f"Result:{len(ans)}")

getResult()

• Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        getResult(t);
    }
    
    public static void getResult(int t) {
        List<int[]> ans = new ArrayList<>();
        
        int[] arr = new int[t];
        for (int i = 0; i < t; i++) {
            arr[i] = i + 1;
        }
        
        int l = 0, r = 1, total = arr[0];
        
        while (l < t) {
            if (total > t) {
                total -= arr[l];
                l++;
            } else if (total == t) {
                int[] exp = new int[r - l];
                for (int i = l; i < r; i++) {
                    exp[i - l] = arr[i];
                }
                ans.add(exp);
                total -= arr[l];
                l++;
                if (r >= t) {
                    break;
                } else {
                    total += arr[r];
                    r++;
                }
            } else {
                total += arr[r];
                r++;
            }
        }
        
        ans.sort((a, b) -> a.length - b.length);
        
        for (int[] an : ans) {
            StringBuilder sb = new StringBuilder();
            sb.append(t).append("=");
            for (int i = 0; i < an.length; i++) {
                sb.append(an[i]);
                if (i < an.length - 1) {
                    sb.append("+");
                }
            }
            System.out.println(sb);
        }
        
        System.out.println("Result:" + ans.size());
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void getResult(int t) {
    vector<vector<int>> ans;
    
    vector<int> arr(t);
    for (int i = 0; i < t; i++) {
        arr[i] = i + 1;
    }
    
    int l = 0, r = 1, total = arr[0];
    
    while (l < t) {
        if (total > t) {
            total -= arr[l];
            l++;
        } else if (total == t) {
            ans.push_back(vector<int>(arr.begin() + l, arr.begin() + r));
            total -= arr[l];
            l++;
            if (r >= t) {
                break;
            } else {
                total += arr[r];
                r++;
            }
        } else {
            total += arr[r];
            r++;
        }
    }
    
    sort(ans.begin(), ans.end(), [](const vector<int>& a, const vector<int>& b) {
        return a.size() < b.size();
    });
    
    for (auto& an : ans) {
        cout << t << "=";
        for (int i = 0; i < an.size(); i++) {
            cout << an[i];
            if (i < an.size() - 1) {
                cout << "+";
            }
        }
        cout << endl;
    }
    
    cout << "Result:" << ans.size() << endl;
}

int main() {
    int t;
    cin >> t;
    getResult(t);
    return 0;
}