Facebook 电面

Badger96 发表于 2016-7-31 12:38
i = 0时还没把6添加进hashset啊，i = 3时才会把6加进去。你如果一开始先把后面的sum加进去当然会错了

我理解错了。我以为你是先把所有sum放进hash里，然后再找的。放一个找一次是没错的。

最近在复习面试，所以看到面经都想一下写写代码，顺便mark一下自己已经看过了。
和大家交流一下方法，如果有什么错误和改进的地方，希望能得到大家的指正。顺便预祝楼主顺利晋级：）

第一题是LC27 Remove Element https://leetcode.com/problems/remove-element/
用two point应该能解O(n)的解，我并没有remove因为觉得如果可以return的话，可以省去remove的那步

1.     def removeElement(self, nums, val):
   
2.         start, end = 0, len(nums)-1
   
3.         while start <= end:
   
4.             if nums[start] != val:
   
5.                 start += 1
   
6.             else:
   
7.                 nums[start],nums[end] = nums[end],nums[start]
   
8.                 end -= 1
   
9.         return nums[:start+1]

复制代码

第二题应该是 LC 325. Maximum Size Subarray Sum Equals k  的变种
https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
题意没有很清楚是不是只有一个subarray可以满足sum = k，我就当只有一个答案来写了，如果有多个，应该是要建立一个dict，dict[sum] = [list of index] 然后用每个index来输出多种可能,如果不存在，return 0

1. def maxSubArrayLen(nums, k):
   
2.     sumNum = 0
   
3.     dict = {}
   
4.     for i in xrange(len(nums)):
   
5.         sumNum  = sumNum + nums[i]
   
6.         if sumNum == k:
   
7.             return nums[:i+1]
   
8. 
   
9.         elif dict.has_key(sumNum-k):
   
10.             return nums[dict[sumNum-k]+1:i+1]
    
11. 
    
12.         if not dict.has_key(sumNum):
    
13.             dict[sumNum] = i
    
14.     return 0

复制代码

都是原题运气不错啊