热乎的脸经

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

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

第一题可以先过一遍求小于等于target的个数，就是size=1的subset数量，然后sort，并用2sum的方法求可行的最大值和最小值。对每对可行的最大值最小值，求这两个数中间夹着的数N，然后乘以2^N。复杂度nlogn。

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

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

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

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

给出一个positive integer array和一个target number

数组中的数的位置可以变吗？

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

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

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

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

leoloe326 发表于 2018-8-21 11:58
可以，要求返回的是subset的数量，比如[2,7,4,8],target=9
那么有[2],[2,7],[2,4],[2,4,7],[4]一共5个

算法O(n^2)?

感谢分享～顺祝offer～

cexq 发表于 2018-8-21 13:05
算法O(n^2)?

最优nlogn

感谢分享～顺祝offer～

用logn的时间找j?

1. sort(data.begin(), data.end());
   
2. int count = 0, n = data.size();
   
3. for(int i = 0; i < n; i++)
   
4. {
   
5.   auto lower = lower_bound(data.begin() + i, data.end(), target - data[i]);
   
6.   if(lower != data.end())
   
7.    {
   
8.           int j = lower - data.begin();
   
9.           count += power(2, j - i -1);
   
10.    }
    
11. }
    
12. 
    
13. return count;

复制代码