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

twosumii 发表于 2017-8-4 07:27
并不是新题，你刷的不够 >

层主two pointer玩得出神入化，钦佩。我一开始也想歪了，往subset上想。

Darkduke68 发表于 2017-8-4 11:25
two pointers 正解。 不过 while 条件我觉得应该是i

双指针做不了吧， 需要 递归
比如 k = 10

当前是 1, 2, 3, 8
1 + 8 = 9 < 10 那么按照你的 code就是 先求出以 1， 8 为边界的集合总数， 然后 把 左边的指针指向 2

但是这样的话 [1, 3] (以1， 3 为边界)的情况 就被 skip了

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

所以 如果 s[i] + s[j] < K的 话， 需要 考虑两种情况， 一种是 i++， 另一种是 j--

mameko 发表于 2017-8-4 19:35
层主two pointer玩得出神入化，钦佩。我一开始也想歪了，往subset上想。

哈哈，可是你拿了offer我挂了，呜呜

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

以前有个大神的id叫twosum， 不知层主是不是他小号？

cynthiazp 发表于 2017-8-5 01:34
以前有个大神的id叫twosum， 不知层主是不是他小号？

是吗？不是啦，，我是看twosum被注册了...就换个题。

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

感觉第二题被玩坏了，这个不是two pointer，但是不需要递归的，因为他只让你求几种方法

数一数有多少个子集（subset）使得子集里面的最大元素加上最小元素小于K。
A: [2, 3, 5, 7]  K: 8
=> # of subsets S: Max(S) + Min(S) < K
=> [2] , [2, 3], [2, 5], [2, 3, 5], [3] => #: 5
在集合[3]里面算有几个数？一个？

Darkduke68 发表于 2017-8-4 11:25
two pointers 正解。 不过 while 条件我觉得应该是i

循环内得再加一个判断吧?
if (i  == j) {
if (s[i] < k) res++;
return res;
}

我自己想一开始用的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.     }

复制代码