谷歌newgrad电面

dengzeyu147 发表于 2019-10-1 13:03
按照老哥说的做法做了一下 请问为何一开始map.put(0,-1)  请老哥指点

[mw_shl_code=java,true] publi ...

抱歉代码改天再看，put(0, -1)是为了处理当前i个数的和为k的情况，sum - k = 0，

dengzeyu147 发表于 2019-10-1 13:03
按照老哥说的做法做了一下 请问为何一开始map.put(0,-1)  请老哥指点

[mw_shl_code=java,true] publi ...

简单看了一下，说的不一定准确：
第一个就是你没有给数组A和B赋初值，默认是0，这样line41取小操作可能会误取，建议初始化为-1，再在31行前面加一个判断
第二个就是line17和33的内部循环应该是没有必要的，可以考虑在数组AB里存放当前index对应的index的值，因为map里面存放的就是最近一次看见的prefix sum，所以对于当前的index如果存在sum-k，那么cache的index就应该是对于当前index最小的interval

yaoyj11 发表于 2019-9-28 19:47
复杂度是O(N)。 从前往后找出前i个数最小的interval， A。再从后往前找出后j个数最小的interval， B[j]。  ...

请问相应的在建B的时候，是不是也需要在map里put（0,n）啊？

spotti 发表于 2019-10-1 01:24
我试着写了一下c++的实现，楼主的testcase能过，不知道是否正确。
**** 本内容被作者隐藏 ****

第二个循环里面的j-1似乎会越界？

mango1290 发表于 2019-10-4 03:11
第二个循环里面的j-1似乎会越界？

不会，j > 0

按照楼上讨论的hashmap O(n)解法，贴一个python版自己写的。思路参考刷题网 伍溜霖
class Solution(object):
        def minSubarray(self, arr, K):
                n=len(arr)
                preSum=0
                A={0:-1}
                B={0:0}
               
                minlenA=[float('inf')]*n
                localmin=float('inf')
                for i in range(n):
                        preSum+=arr[i]
                        if preSum-K in A:
                                if i-A[preSum-K]<localmin:
                                        minlenA[i]=i-A[preSum-K]
                                        localmin=i-A[preSum-K]
                        A[preSum]=i
               
                preSum=0
                minlenB=[float('inf')]*n
                localmin=float('inf')
                for j in range(n)[::-1]:
                        preSum+=arr[j]
                        if preSum-K in B:
                                if n-j-B[preSum-K]<localmin:
                                        minlenB[j]=n-j-B[preSum-K]
                                        localmin=n-j-B[preSum-K]
                        B[preSum]=n-j
               
                res=float('inf')
                for k in range(n):
                        if k==0:
                                cur=minlenB[0]
                        else:
                                cur=minlenA[k-1]+minlenB[k]
                        if cur<res:
                                res=cur
               
                return -1 if res==float('inf') else res

类似蠡口溜酒吧~

spotti 发表于 2019-10-1 01:24
我试着写了一下c++的实现，楼主的testcase能过，不知道是否正确。
**** 本内容被作者隐藏 ****

求问left的初始为什么是（0， -1）

今天new grad 电面遇到相同的题目。。。以后应该好好看面经orz

我一开始也是enumerate interval， filter those that sum up to k，use pivot in between to separate left and right
复杂度大概n^2

我提到array都是》0的 我于是想到可以sliding window找target k， 国人面试官提示我可以用一个shortest【i】存 input【0..i】最短的符合条件的interval length  
最后的确可以 linear space and time
left【i】 = shortest len subarray summing to k in input[0..i]


right【i】 = shortes len subarray summing to k in input[i.. end]


sliding window to build two arrays above


then for i in 1.. end-1 :  shortest = min(shortest, left[i -1 ] + right[i +1])


code 写不完 国人面试官也太好了说：你先问问题，然后我去meeting（此时面试已1小时），你接着写，我回来看你code即可
最后写了90% 和手动testcase 也不一定bug free，但沟通真的很愉快 国人面试官令人感动