最新华为OD机试真题-整数的连续自然数之和表示(100分)

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

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

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

📎在线评测链接

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

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

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

问题描述

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

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

输入格式

输入一个正整数 。

输出格式

按照题目要求，输出所有表示 的方案，每个方案占一行。最后一行输出 Result: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

数据范围

题解

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

初始时，，，，其中 是从 到 的所有自然数组成的数组。

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

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

时间复杂度 ，空间复杂度 。

参考代码

• 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];