Facebook电话面

SXY123 发表于 2017-10-10 12:20
求LZ发一下双指针的解法？感觉难度很大，怎么写都不对

应该是类似sliding window吧？

SXY123 发表于 2017-10-10 12:20
求LZ发一下双指针的解法？感觉难度很大，怎么写都不对

写了一个代码，你可看看，对不对= =
array全正数，k也是正数

1. public class SubarraySum {
   
2.        
   
3.         public int equalToKPositive(int[] nums, int k) {
   
4.                 int count = 0;
   
5.                 int sum = 0;
   
6.                 int start = 0;
   
7.                 for(int i = 0; i < nums.length; i++) {
   
8.                         sum += nums[i];
   
9.                         while(sum > k) {
   
10.                                 sum -= nums[start];
    
11.                                 start++;
    
12.                         }
    
13.                         if(sum == k) {
    
14.                                 count++;
    
15.                         }
    
16.                 }
    
17.                 return count;
    
18.         }
    
19.        
    
20.         public static void main(String[] args) {
    
21.                 SubarraySum obj = new SubarraySum();
    
22. //                int[] nums = {0,0,0,1,0,0,0};
    
23.                 int[] nums = {1,2,3,4,1,2,2,2,2};
    
24.                 int k = 4;
    
25.                 System.out.println(obj.equalToKPositive(nums, k));
    
26.         }
    
27. }

复制代码

king_lm 发表于 2017-10-22 05:31
写了一个代码，你可看看，对不对= =
array全正数，k也是正数

如果都是positive，应该是先sort再用双指针，nlogn，你这个写法是n^2了吧。。

补充内容 (2017-11-6 17:26):
忽略我的评论。。之前脑子不清醒，想成two sum了。。。。

用hashtable写吧，时间O(n),空间O(n)

844587076 发表于 2017-11-5 00:47
如果都是positive，应该是先sort再用双指针，nlogn，你这个写法是n^2了吧。。

不是N^2 应该最差是2n 最差的情况是扫2遍 个人感觉

ninepig 发表于 2017-11-6 11:41
不是N^2 应该最差是2n 最差的情况是扫2遍 个人感觉

他那个code是n^2, 譬如要找的sum是整个数组的和，就是n^2