题目分析

1. 题目给定一个数字n
2. 这个数字要求立方值
3. 求得的结果要拆成n个连续奇数和
4. 输出这n个奇数

方法一：暴力

• 实现思路

  • 我们直接从1到n^3建一个奇数列表

  • 然后从奇数列表起点遍历，每次取n个数字和与目标数字比较

  • 最终返回比较成功时的匹配结果

def solution(n):
    l = [i for i in range(1, n*n*n+1) if i&1]                   # 构造到n立方值的所有奇数列
    for i in range(len(l)):                                     # 暴力遍历所有的起点
        if sum(l[i:n+i]) == n*n*n:                              # 尝试结果是否为n^3
            return "+".join(map(str, l[i:n+i]))                 # 返回最终结果
    return ""
    
while True:
    try:
        n = int(input())
        print(solution(n))
    except:
        break

复杂度分析

• 时间复杂度：$O(n^4)O(n^4)$，由于建表的代价为$O(n^3)O(n^3)$，而遍历的代价又是$O(n)O(n)$，因此最终为四次方的带家具
• 空间复杂度：$O(n^3)O(n^3)$，建表大小是三次方的空间开销

方法二：数学推导

• 实现思路
  • 我们可以通过数学推导得出，这一串目标奇数的起始数字为$n^2-n+1n^2-n+1$
  • 然后我们就通过n个数字逐一数出来所有奇数即可

def solution(n):
    num = n*n*n                        # 计算出三次方的值
    mid = int(num / n)                 # 计算出最中间的值
    start = mid - (n-1)                # 推断出每个开始的数字
    l=[]
    for i in range(n):                 # 根据所需的n个数字往后逐个计算出奇数
        l.append(str(start + 2*i))
    return "+".join(l)                 # 返回最终结果
    
while True:
    try:
        n = int(input())
        print(solution(n))
    except:
        break

复杂度分析

• 时间复杂度：$O(n)O(n)$，一次遍历建最终结果的整型数字列表的时间
• 空间复杂度：$O(n)O(n)$， 最终n个整型数字列表的空间开销