谷歌newgrad电面

分享一个狗家电面的数据点

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

谢谢大家~

类似蠡口溜酒吧~

按照楼上讨论的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

yaoyj11 发表于 2019-9-30 05:21
你看利口那到题就知道了 用hash map可以线性时间算出最短的interval 存着，。 i指分割点， A的含义是前i个 ...

按照老哥说的做法做了一下 请问为何一开始map.put(0,-1)  请老哥指点

1. public int subarraySum(int[] nums, int k) {
   
2.         int len = nums.length;
   
3.         if(len == 0)return 0;
   
4.         HashMap<Integer,Integer> map = new HashMap<>();//key sum, value; start
   
5.         map.put(0,0);
   
6.         int sum = 0;
   
7.         //int count = 0;
   
8.         int[] A = new int[len];
   
9.         int[] B = new int[len];
   
10.         int minInterval = Integer.MAX_VALUE;
    
11.         for(int i = 0; i < len; i++) {
    
12.             sum += nums[i];
    
13.             if(map.containsKey(sum - k)){
    
14.                 int start = map.get(sum-k);
    
15.                 int interval = i - start ;
    
16.                 minInterval = Math.min(minInterval,interval);
    
17.                 for(int j = start; j<= i; j++)A[j] = minInterval;
    
18.             }
    
19.             map.put(sum,i);
    
20.         }
    
21.         
    
22.         map = new HashMap<>();
    
23.         minInterval = Integer.MAX_VALUE;
    
24.         sum = 0;
    
25.         map.put(0,len-1);
    
26.         for(int i = len-1; i >= 0; i--) {
    
27.             sum += nums[i];
    
28.             if(map.containsKey(sum - k)){
    
29.                 int start = map.get(sum-k);
    
30.                 int interval = start - i + 1;
    
31.                 minInterval = Math.min(minInterval,interval);
    
32.                
    
33.                 for(int j = start; j >= i; j--)B[j] = minInterval;
    
34.             }
    
35.             map.put(sum,i);
    
36.         }
    
37.         
    
38.         int res = 20000;
    
39.         for(int i = 1; i < len; i++){
    
40.             int temp = A[i-1] + B[i];
    
41.             res = Math.min(temp,res);
    
42.             System.out.println((i-1) + " " + i + " " +temp);
    
43.         }
    
44.         
    
45.         return res;
    
46.     }

复制代码

多谢分享

谢谢分享，这个刷题网还是很多类似的题， 先从前往后一遍求前i个数中最短的interval， 再从后往前一遍算后n-i中最短的interval 然后对每个i算左右总数最小的

yaoyj11 发表于 2019-9-28 06:04
谢谢分享，这个刷题网还是很多类似的题， 先从前往后一遍求前i个数中最短的interval， 再从后往前一遍算后n ...

想问一下这个思路是蠡口什么题的呀。。
只记得有 subarray sum equals K。。感谢
这样是 对每个位置为分割点，找一次最小length 和，时间 N^2? 我现在想的是，找左侧右侧 subarray equals K 用 sliding window做。。不知道hashmap好不好用

同时想问LZ，都找到了什么 corner case。感谢感谢

savage811 发表于 2019/09/28 14:07:13

想问一下这个思路是蠡口什么题的呀。。
只记得有 subarray sum equals K。。感谢
这样是 对每个位置为分割点，找一次最小length 和，时间 N^2? 我现在想的是，找左侧...

复杂度是O(N)。 从前往后找出前i个数最小的interval， A[i]。再从后往前找出后j个数最小的interval， B[j]。 最后对于每个i， 求A[i—1]＋B[i]。 corner case，除了数组长度小于2，想不出了，overflow应该不是重点， 利口上的题都没有这种overflow的test case。不过这个题容易忘记开始时在hash map里put(0, -1),  不知道楼主遇到了什么corner case。

补充内容 (2019-9-28 11:49):
就是说的这道，

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

请问一下i是指分割点吗？如果是分割点分话通过不断的找i，复杂度不是N^吗？谢谢解答！！

mona0101 发表于 2019/09/30 03:45:40
请问一下i是指分割点吗？如果是分割点分话通过不断的找i，复杂度不是N^吗？谢谢解答！！

你看利口那到题就知道了 用hash map可以线性时间算出最短的interval 存着，。 i指分割点， A[i]的含义是前i个数和为k的最小interval。B类似， 这样对每个i，只需读i左右两边的数。复杂度N。多加点米谢谢

我试着写了一下c++的实现，楼主的testcase能过，不知道是否正确。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

只返回两段吗？