google电面，直接把我和面试官面时候的google doc复制下来给大家看

第二题如果是3sum的话（找三个数的和正好等于k），time complexity可以减少到n^2，用hash table。
但是这个题问<k，有小于n^3时间的算法吗？没想出来。。。any suggestions?

弱弱的问下，是他把问题打在docs里还是，在电话里用语音说的。。。。我怕一紧张就听不清对方说啥了

fanfeng 发表于 2016-5-18 10:50
第二题如果是3sum的话（找三个数的和正好等于k），time complexity可以减少到n^2，用hash table。
但是这 ...

先取第一个数，后面两个用两个pointer，一个从头一个从尾，往中间找，n^2

fanfeng 发表于 2016-5-17 21:50
第二题如果是3sum的话（找三个数的和正好等于k），time complexity可以减少到n^2，用hash table。
但是这 ...

可以n^2logN做

刚刚拿python写了下第二题。output 没有问题，但不知道我的思路对不对？
complexity要求也达到了

另外楼主运气好好~希望我后面的运气也这样：））

1. def sumSmaller(nums,input):
   
2.         result = []
   
3.         i=0
   
4.         count = 0
   
5.         while i < len(nums)-1:
   
6.                 if i == 0 or nums[i]!=nums[i-1]:
   
7.                         j= i+1
   
8.                         k=len(nums)-1
   
9.                         while j<k:
   
10.                                 if nums[i]+nums[j]+nums[k]<input:
    
11.                                         result.append([nums[i],nums[j],nums[k]])
    
12.                                         count +=1
    
13.                                         j+=1
    
14.                                         k=len(nums)-1 #so once i found the "<" as required. i will count from the last item compare against j
    
15.                                 elif nums[i]+nums[j]+nums[k]>=input:
    
16.                                         print("been here")
    
17.                                         k-=1
    
18. 
    
19.                 i+=1
    
20.         print(count)
    
21.         return result
    
22.                
    
23.        
    
24. 
    
25. nums = [5, 3, 6, 1, 8, 10]
    
26. print(sumSmaller(nums,13))

复制代码

补充内容 (2016-8-26 17:13):
忽略我写的“print been here。”单纯test code...sorry la~

claireyangyang 发表于 2016-8-26 17:11
刚刚拿python写了下第二题。output 没有问题，但不知道我的思路对不对？
complexity要求也达到了

没太明白这个逻辑，如果nums不是sorted怎么进行的j++和k--呢？

第二题，先排序，然后按照3sum做，O(N^2)~~

O(n^2 log n)
3sum的思路+binary search

luofeidream 发表于 2016-10-24 05:22
第二题，先排序，然后按照3sum做，O(N^2)~~

是啊 排序之后 two pointers 就可以了

唯一麻烦的是 two pointers 的解法 justify 起来总是麻烦点，需要证明不会忽略符合条件的组合

这样把题目复制粘贴过来不太好吧，会不会影响到那个善良的小哥