"Memory limit exceeded" 和 "Time limit exceeded" 在 Python 中的问题

Question

我有一个问题要在 online judge 上解决。它的解决方案是使整数的总和例如输入4，所以1 + 2 + 3 + 4输出10。再例如，输入是10，所以得到1到10的总和得到输出55和等等。

但是当我使用 list 来存储数字并求和（List）时，它给了我一个 “超出内存限制” .

代码如下：

n = int(raw_input())
lista = []
for x in range(1, n+1):
   lista.append(x)
print sum(lista)

我尝试了另一种解决方案，不保存在列表中以避免内存超出，所以我尝试了这个：

n = int(raw_input())
sum = 0
for i in xrange(1, n+1):
   sum = sum + i
print sum

但是我收到“超出时间限制”。这个问题的解决方案是什么？

请注意，输入的数字范围是 1≤ N ≤ 10^9。当我尝试 10^9 时，需要很长时间才能得到答案。

另外需要注意的是每次测试的时间限制是1秒

Answer 1

这是等差级数，计算方式为 S = ½(a1 + an)n，其中 a1 是第一个成员，在本例中为 1。一个是最后一个在这种情况下是 n 的成员。

def arthimPSum(n):
    return round((1 + n)*n *0.5)

print(arthimPSum(10**9))

500000000500000000

Problem of "Memory limit exceeded" and "Time limit exceeded" in Python