我之间的问题严重受到质疑。有什么建议？我尝试下面的代码：
def getSum(A, n, m, x, y):
res = 0
for row in range(n + 1):
for col in range(m + 1):
if col <= y:
res += A[row][col]
return res
问题是你试图迭代整个矩阵，“过滤掉”你不需要的值。而不是那样，你应该尝试只迭代你需要的值，在这种情况下，这是可能的，而不是很难。你需要从行索引0到x，所以你可以使用for row in range(x + 1)。对于列，您必须遍历所有这些（最多m - 1）行0到x - 1，并且只有y行行索引x。您可以将其计算为last_col = m - 1 if row < x else y，然后像for col in range(last_col + 1)一样迭代。然后，您只需对迭代的所有值求和，因为您不需要“过滤”其中任何值：
def getSum(A, n, m, x, y):
res = 0
for row in range(x + 1):
last_col = m - 1 if row < x else y
for col in range(last_col + 1):
res += A[row][col]
return res
注意：n和m参数在函数中并不是必需的，我保留它们来维护你提出的相同的函数原型，但是如果你需要决定你需要什么参数，你就会把它们排除在外。即使你需要它们，你也可以使用A从len获得它们。
注2：我只考虑计算有效输入集的结果的问题。请记住，在这种测试中很多次，面试官想要检查你如何处理不良输入（负数，无效大小，None等）和角落情况。
注3：如果你想要你可以在一个单行中做所有事情，虽然老实说它可能会更难阅读，我不确定面试官会欣赏这一点。您还可以考虑使用中间选项。无论如何，上面的函数体可以压缩为：
return sum(sum(A[row][col] for col in range(m if row < x else y + 1)) for x in range(x + 1))
好吧，你可以通过创建另一个NxM矩阵来改善这一点，其中(x, y)中的元素将包含从原始矩阵的(0, 0)到(x, y)的元素之和。创建此矩阵后，您只需查找即可回答任何查询。
现在，将有MN值来计算。如果你试图总结子矩阵中的所有值，那么在每种查询的最坏情况下都需要O((MN))时间。但是通过一些memoization，它可以使用动态编程在O(MN)时间生成，然后每个查询都可以在O(1)时间回答。
该解决方案依赖于简单的递归关系（S[x][y]表示从(0, 0)到(x, y)的A元素之和）：
S[0, 0] = A[0, 0]
S[0, y] = S[0, y - 1] + A[0, y] when y > 0
S[x, 0] = S[x - 1, 0] + A[x, 0] when x > 0
S[x, y] = S[x, y - 1] + S[x - 1, y] - S[x - 1, y - 1] + A[x, y] when x, y > 0
关键点是，从(0, 0)到(x, y - 1)以及从(0, 0)到(x - 1, y)的子矩阵的总和都包含从(0, 0)到(x - 1, y -1)的子矩阵的总和，所以我们将它加两次。这就是我们需要减去一次的原因。
所以它的代码应该很简单：
def sumMatrix(A):
S = [[0 for i in range(len(A[j]))] for j in range(len(A))]
S[0][0] = A[0][0]
for i in range(1, len(A)):
S[i][0] = S[i - 1][0] + A[i][0]
for j in range(1, len(A[0])):
S[0][j] = S[0][j - 1] + A[0][j]
for i in range(1, len(A)):
for j in range(1, len(A[0])):
S[i][j] = S[i][j - 1] + S[i - 1][j] - S[i - 1][j - 1] + A[i][j]
return S
一旦调用此方法，您可以通过查找来回答O(1)中的任何查询！
它也可以缩短一点：
def sumMatrix(A):
S = [[A[i][j] for i in range(len(A[j]))] for j in range(len(A))]
for i in range(0, len(A)):
for j in range(0, len(A[0])):
if i > 0:
S[i][j] += S[i - 1][j]
if j > 0:
S[i][j] += S[i][j - 1]
if i > 0 and j > 0:
S[i][j] -= S[i - 1][j - 1]
return S
import numpy as np
array = np.random.rand(20, 20)
list = array.tolist()
def get_sum_numpy(x, y):
return np.sum(array[:x, :y])
def get_sum_list(x, y):
total = 0
for i in range(x):
for j in range(y):
total += list[i][j]
return total
print(get_sum_numpy(4, 5))
print(get_sum_list(4, 5))
这是我提出的快速解决方案。使用numpy更有效，但也有一个没有第三方库的解决方案。
a = [[1,2,3], [4,5,6], [7,8,9]] # a 3x3 Matrix
sum = 0
# entered string (3,1)
# calculating sum from (0,0) till the given
for i in range(0, len(a)):
for j in range(0, len(a[i])):
if (i+1)>=3:
if (j+1)>=1:
break
else:
sum += a[i][j]
print (a[i][j])
你可以这样做：
getSum(A, n, m, x, y):
if (x >= n):
# x is out of bounds. Do some error handling here
if (y >= m):
# y is out of bounds. Do some error handling here
return sum( [ sum(col[:y]) for col in A[:x] ] )
这使用列表推导从索引0到x抓取A中的每一行，然后计算从0到y的每一行的总和，并计算这些总和的总和。
顺便说一句，如果您事先已经检查了x < n和y < m，则不需要将它们用作函数的参数。