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

edyyy 发表于 2017-8-5 11:00
数一数有多少个子集（subset）使得子集里面的最大元素加上最小元素小于K。
A: [2, 3, 5, 7]  K: 8
=> #  ...

3+3<8
所以应该是一个

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

scredwood 发表于 2017-8-4 13:13
如果你实在想双指针，那么就先预处理把重复去掉咯。。。

有重复的情况
预先处理掉的话， 2 3 3 5
3的重复可以去掉，但是会漏掉 2 3 3，2 3 3 5, 3 3这几个答案。
是不是有重复的时候 我们就要把 subset用backtracking找到具体不重复答案有几个？

LZ面的是哪个组？是那个做business app的组吗？

真淘蛮 发表于 2017-8-5 13:17
循环内得再加一个判断吧?
if (i  == j) {
if (s < k) res++;

不需要加吧，while (i <= j) 已经把单一元素的情况包括了。 详情看下楼的code, 一个意思。

补充内容 (2017-8-6 13:26):
30楼的code

twosumii 发表于 2017-8-5 00:28
哈哈，可是你拿了offer我挂了，呜呜

我刚好碰到做过的题，比较幸运而已。

pomme2016 发表于 2017-8-5 13:27
我自己想一开始用的DP，然后发现真的可以双指针呢。
感觉下面写的代码是对的，跑了几个test case

当 i == j 时, if (nums[i] + nums[j] < K) 要转化成 if (nums[i]  < K) 吧

Darkduke68 发表于 2017-8-6 13:25
不需要加吧，while (i

nums = { 1}, k = 2 呢, 30楼的code , 跑完是0?

第二题双指针是可以，但是不能简单数学方法算subset，会有很多重复的啊。。。

自己写的，比较直接的解法：

1. import java.util.*;
   
2. 
   
3. // 给一个排序好的数组，数一数有多少个子集（subset）使得子集里面的最大元素加上最小元素小于K。
   
4. // A: [2, 3, 5, 7]  K: 8
   
5. // => # of subsets S: Max(S) + Min(S) < K.
   
6. // => [2] , [2, 3], [2, 5], [2, 3, 5], [3] => #: 5
   
7. 
   
8. class LessThanK{
   
9.     public static void main(String[] args) {
   
10.         int[] nums = {2,3,3, 5, 7};
    
11.         int k = 8;
    
12.         LessThanK test = new LessThanK();
    
13.         int res = test.getNumber_noDuplicate(nums, k);
    
14.         System.out.println(res);
    
15.       
    
16.         System.out.println("Backtracking Way:");
    
17.       
    
18.         int res2 = test.getNumber_dfs_Duplicate(nums, k);
    
19.         System.out.println(res2);
    
20.     }
    
21. 
    
22.     // ========= if No Duplicate ===========
    
23.     public int getNumber_noDuplicate(int[] nums, int k) {
    
24.         int cnt = 0;
    
25.         int i = 0, j = nums.length - 1;
    
26. 
    
27.         while (i <= j) {
    
28.             if (nums[i] + nums[j] < k) {
    
29.                 cnt += (int) Math.pow(2, j - i);
    
30.                 i++;
    
31.             } else {
    
32.                 j--;
    
33.             }
    
34.         }
    
35. 
    
36.         return cnt;
    
37.     }
    
38. 
    
39.     // ========= With Dulicate, like Combination Sum II  ========= ：

复制代码

补充内容 (2017-8-6 09:42):
next page （cont..）