目录
11.Container With Most Water【Medium】
题目：
解题思路：
没有叫你返回具体坐标，只要求最大面积的话，那么用一个变量记录下，然后两边开始往中间移动
对于长边来讲，往里边移动一个坐标，无论更长或者更短，都不会使面积变大，所以每次都移动短边，这样每移动一次，最大面积都有可能更新
Tip:如果不采用两边移动的话，就是要进行两两遍历，也就是O(n2), 两边移动就是O(n)
code:
1 def maxArea(self, height): 2 """ 3 :type height: List[int] 4 :rtype: int 5 """ 6 i = 0 7 j = len(height)-1 8 maxarea = 0 9 while i < j: 10 maxarea = max((j-i)*min(height[i],height[j]), maxarea) 11 if height[i] < height[j]: 12 i += 1 13 else: 14 j -= 1 15 return maxarea
15. 3Sum【Medium】
题目：
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero
解题思路：
做2Sum的时候用的是hash算法O(N)就可以做完，那么这个3Sum其实就是一个O(N)的2Sum, 于是乎就是O(N*N)的算法
2Sum算法如下：O(N)
所以3Sum只需进行O(N)次2Sum就行了，写个循环完成
Tip:数组题要是涉及到找数字，记得用hash法，用空间换时间
code:
1 def threeSum(self, nums): 2 """ 3 :type nums: List[int] 4 :rtype: List[List[int]] 5 """ 6 length = len(nums) 7 if length < 3: 8 return [] 9 result = [] 10 nums.sort() 11 for i in range(length-2): 12 if i>0 and nums[i]==nums[i-1]: 13 continue 14 hash_table = {} 15 res = 0-nums[i] 16 for j in range(i+1,len(nums)): 17 if j>3 and nums[j]==nums[j-3]: 18 continue 19 if nums[j] in hash_table: 20 result.append([nums[i],res-nums[j],nums[j]]) 21 hash_table.pop(nums[j]) 22 else: 23 hash_table[res-nums[j]] = nums[j] 24 return result
哇，这道题处理重复很头疼啊,对于[1,0,-1,1]结果为[[1,0,-1],[0,-1，1]]显示说答案错误
如果找到一组解的时候，在result里面查询是否已经存在的话就会多一层循环，结果会超时。
所以这里预先将数组进行排序，让可行的结果呈顺序状，更好地防止结果重复。
但是面对大量重复数字的时候，出现很多问题， 比如[0,0,0,0,0,0,0,0,0,0,0,0], [-4,2,2,2,2,2,2,2,3]
这里就要求固定第一个数字的时候，希望不重复，也就是要跳过nums[i]==nums[i-1]的情况
对于第二个数字呢，因为只要求2sum，所以对于重复大于3的情况不需要考虑。即跳过nums[j]==nums[j-3]
很奇怪为什么我的算法ac时间很长，统计数据只打败了2.9%提交的python代码，看下别人的解法
code_writen_by_others:
1 def threeSum(self, nums): 2 """ 3 :type nums: List[int] 4 :rtype: List[List[int]] 5 """ 6 length = len(nums) 7 if length < 3: 8 return [] 9 result = [] 10 nums.sort() 11 for i in range(length-2): 12 if i>0 and nums[i]==nums[i-1]: 13 continue 14 res = 0 - nums[i] 15 low = i+1 16 high = length-1 17 while(low < high): 18 if(nums[low]+nums[high]==res): 19 result.append([nums[i],nums[low],nums[high]]) 20 while(low<high and nums[low]==nums[low+1]): 21 low += 1 22 while(low<high and nums[high]==nums[high-1]): 23 high -= 1 24 low +=1 25 high -=1 26 else: 27 if(nums[low]+nums[high]<res): 28 low += 1 29 else: 30 high -= 1 31 return result
我好笨啊，因为已经排好序了，所以没必要用hash,直接两头做加法往中间移动，比hash省了空间还省了时间
但是2Sum用hash更好，因为排序算法是O(NlogN)的，hash是O(N)的，所以追求效率的话还是hash
原文：http://www.cnblogs.com/lainey/p/7741583.html