刚刚字节跳动一道题
二维数组
1 2 3
4 5 6
7 8 9
10 11 12
(3,3) - (2,2)即5+6+8+9
(4,3) - (2,2)即5+6+8+9+11+12
求(x1,y1)-(x2,y2),不能遍历
dp,大家有什么好的方法吗,大矩形减三个小矩形吗?
百度没搜到
#字节跳动##笔试题目##秋招#
关注
全部评论
Jonariguez
拼多多_算法工程师
dp[i,j]表示左上角是(1,1)，右下角是(i,j)的矩形的和，然后dp[x1,y1]-dp[x1,y2 -1]-dfp[x2 -1,y1]+dp[x2 -1,y2 -1]就可以了，可以O(1)
lovelyy
东南大学 后端
这不就是我实习的题么，上面那个老哥的答案就是对的
Jonariguez
拼多多_算法工程师
反正还是矩形减减加加呗😂
loongll
北京邮电大学
二维前缀和
相关推荐
，这工资还不如去摇奶茶 
投递三一重能等公司6个岗位 > 点赞 评论 收藏
分享