拼多多一面(8.31 16:00)
上来先问力扣刷的怎么样,然后手撕给我撕红温了。面试官超有耐心,让我再想想再想想,还会提示一下,可惜我太菜了
1. 自我介绍
2. 手撕
2.1. 给定一个数组,给定两个子数组的首尾索引(i,j)和(m,n),数组元素不会变,但子数组索引会经常变动,求两个子数组元素之和(重合的元素只求一次)
最开始说用 HashSet,放进去后求和,但因为索引会经常变动,然后面试官说换一种思路
后面说前缀和,面试官说还有其他的思路
2.2. 给定一个数组,给定一个 i 和 j,i 和 j 会频繁变化,找出这个子数组中的最大元素
同理不能用普通遍历求解,不能暴力
搜了一下什么线段树,没了解过