脸家加面，似乎他家最近新题很多？

上次国人大哥给了个新题，想了一会给了解答，feedback是problem solving不够好。 这次加面还是国人面试官，似乎又一个新题。

简单自我介绍了一下直接上

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

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

3], [2, 5], [2, 3, 5], [3] => #: 5


尽人事听天命了，唉~~

我自己想一开始用的DP，然后发现真的可以双指针呢。
感觉下面写的代码是对的，跑了几个test case

1. public int subarraySum(int[] nums, int K) {
   
2.         if (nums == null || nums.length == 0 || nums[0] * 2 >= K) {
   
3.             return 0;
   
4.         }
   
5.         int sum = 0, i = 0, j = nums.length - 1;
   
6.         while (i <= j) {
   
7.             if (nums[i] + nums[j] < K) {
   
8.                 sum += (int)Math.pow(2, j - i);
   
9.                 i++;
   
10.             } else {
    
11.                 j--;
    
12.             }            
    
13.         }
    
14.         return sum;
    
15.     }

复制代码

并不是新题，你刷的不够 ><。   其实吧，跟第一题有那么一点联系？ 你排好序，然后two pointer, 当找到 a[i] + a[j]  < k,  && i < j 的时候，包含i的子集有 2^(j-i) 个，他们都满足条件。 然后i++，继续看，否则j--， O（n）就够了

补充内容 (2017-8-4 07:28):
while (i < j)
   if (a[i] + a[j] < k)   count += Math.pow(2, j-i); i++
   else j--


补充内容 (2017-8-4 07:29):
是 a [ i ],   一亩三分地会吧 [ i ] 当成斜体，弄没掉了  a =  a/[i/]

stealop 发表于 2017-8-4 22:34
双指针做不了吧， 需要 递归
比如 k = 10

这题感觉是subset变形。
1 2 3 8的 1+8<10的时候 2^3 = 8是有8个subset 1, 1 2, 1 3, 1 8, 1 2 3, 1 2 8, 1 3 8, 1 2 3 8
然后下一个2 + 3<10 的时候 2个解 2， 2 3
然后是 3 + 3 <10 的时候 3 一个解
一共11个subsets

第二道题backtracking嘛楼主？求解法

第二题求所有最大windows, 然后计算子集而已

补充内容 (2017-8-4 07:32):
等一下看错题了，以为是最大元素，最小元素差要小于k
和小于k的话，可以用two pointers, 不是有道相似的计算pairs的题吗
、

其实这题也是面经题

33847682 发表于 2017-8-4 07:32
其实这题也是面经题

请问是哪里看到的，我也错过了

edyyy 发表于 2017-8-4 07:34
请问是哪里看到的，我也错过了

忘记是什么时候了 之前地里的面经

尝试了一下第二题, 思路就是分别数如果当前list最小数进subset or not 然后recur


class Solution():
        def nSubsets(self,nums,k):
                if nums==None or k==None or k<=min(nums):
                        return -1
                def count(l):
                        if l==None:
                                return 0
                        if 2*l[0]>=k:
                                return 0
                        i=1
                        while i<len(l) and l[0]+l[i]<k:
                                i+=1
                        return 2**(i-1)
                def rec(nums):
                        if not nums:
                                return 0
                        ans=0
                        ans+=count(nums)+rec(nums[1:])
                        return ans
                return rec(nums)


补充内容 (2017-8-4 08:02):
看来不用这么麻烦 直接2pointers就够了 刷的还是不够熟练啊-.-

第二题和two sum一样的解法

首先window = [S[0], S[-1]]，如果超了，那就缩小上限，直到满足条件；然后一个一个的递增下限，直到条件条件不满足为止

补充内容 (2017-8-4 08:18):
似乎有问题，这个是找出所有集合，那还是先暴力搜吧。

补充内容 (2017-8-4 08:25):
呃，two pointers依然可以做，实际上就是找出所有的满足(x, y), 其中x + y < K的数对就行了，因为数组是排序过的，所以找出这些pair之后，就可以算出，中间有多少数，然后subset的个数就是2^(ix - iy - 1)个。

补充内容 (2017-8-4 08:31):
要考虑一个元素时候的特殊情况

楼主第二题，result得加上5和7.