m**********e
发帖数: 52 | 1 一个看名字是南美人面的，给定一个数组，一个目标数，判断这个数组中是否存在连续
的数之和等于目标数，比如[1,2,3,4], t=5, 返回true （2+3=5）. 第一反应是维护一
个滚动窗口，于是问了里面的数字有没有可能是负数，因为他给的例子都是正数，他说
可能是负数；这样的话貌似没法这么做，于是给了个n^3的，知道不好，后来就是把
check sum = target那部分放到第二个loop, 边加边判断，优化到n^2, 他也认可了。
后来他说能不能更加优化，我就想不出来了，后来他说那假设里面的都是正数或者0吧
，我于是匆匆忙忙写了个滚动窗口的解，O(N)，但因为时间就到了，简单写了几个测试
，感觉可以，但估计有bug，就不了了之了。
感觉他就是想要滚动数组的解法，估计没想到负数的情况？还是就算有负数也能做到O(
n)? 整个45分钟就做了一道题，聊了下做过的project啥的，估计已经跪了，希望其他
几家onsite能够给力点，发个面经攒点人品吧。 | k****i
发帖数: 128 | | n******n
发帖数: 12088 | 3 不需要hash map
【在 k****i 的大作中提到】
: 最优解是hashmap存partial sum
| d*****c
发帖数: 605 | 4 存hashset就好了，存sum(i,0).
然后用j在跑，得到target = sum(j,i) = sum(i,0) - sum(j,0)，在hashset里面有没
有 sum(j,0) + target就好了啊 | v*****y
发帖数: 68 | | y*******3
发帖数: 158 | | x*****n
发帖数: 195 | |
|
