1. Two Sum

用hash可以得到O(n)时间的解法，用python中的enumerate函数，可以获得元素的值及其坐标，通过dic[target - x] = i，将元素存入字典中，x最终一定会出现在dic里，然后返回当前的i，和dic[x]，dic[x]就是回溯，去找之前第一次出现的x'
Time complexity: O(n)

4. Median of Two Sorted Arrays

• 这道题可以扩展为寻找数列中的第k小元素，这里的k就是(len(nums1) + len(nums2))//2, 注意在python里：//就是整除，只保留商的整数部分，如果想要获得小数结果，除数和被除数就至少应该有一个是float型，5/2.0 = 2.5, 5/2 = 2
• 首先要判断两个数组的总长度是odd还是even，如果是odd,那就是找(l/2)小的元素，l是两个数组的总长度。如果是even，那就是找（第l/2小 + 第l/2-1小)/2
• 寻找第k小元素：如果有一个数组不存在，就直接返回另一个数组的第k个元素。如果两个数组都存在，首先取各自长度的一半做下标，找到每个数组的median，然后判断两个下标的和与K的大小关系
• 如果l1 + l2 < k，并且if m1 > m2:, 就去掉较小数组的前半段，并且更新k！！！ k = k - l2/l1 -
  如果l1 + l2 > k, 就去掉较大数组的后半段。
  Time complexity: O(log(m+n))

15. 3Sum

固定一个元素，然后对剩下两个元素进行夹逼的方法。复杂度：O(n^2)

• 注意要先对数组排序才行
• for循环中的i只能取到len(nums)-2之前一个数。
• for循环一开始先检测if i>0 and nums[i] == nums[i-1]: continue，这样可以避免出现重复结果
• 当找到三个数相加为0时，也要避免出现重复结果，进行如下检验：
  while left < right and nums[left] == nums[left+1]: left += 1 while left < right and nums[right] == nums[right-1]: right -= 1

16. 3Sum Closest

跟第15题用的方法相似，也是固定一个元素然后进行夹逼。不同的是这道题要求找到与target最相近的元素和。所以我们应该初始化一个元素和，用它来做标准，通过之后的比较进行更新。
glo = nums[0] + nums[1] + nums[2]
因为这道题只有唯一解，所以不需要判断重复元素，每次直接更新Left和right就可以。

• 需要注意的点就是，每次得出sum后，要和glo进行绝对值比较：
  if abs(sum - target) < abs(glo - target): glo = sum
• while循环条件不要忘了while left < right

18. 4Sum

Time Complexity: O(n^2)
two sum + two sum = four sum

• 维护一个value类型为List的hash table。将array里的元素两两相加，并将得到这个和的两个元素的下标作为value对存进去。因为两两相加的结果可能会有重复的，所以每个value的类型是list，会存很多个下标对
• 两两相加结束后，就开始处理hash里的值。用dic.iteritems()这个迭代器取得key和value，key就是two sum，用target减去two sum，得到dif, 即另一个two sum。然后根据这个two sum，取得它对应的下标对，如果对应的下标对为空，就continue。若不为空，便对两个下标对组合进行遍历。
  for p1 in pair1:
  for p2 in pair2:
  i1, j1 = p1
  i2, j2 = p2
  if i1 in p2 or j1 in p2:
  continue
• 这里的if判断非常重要，因为两个two sum的值可能完全相同，比如4等于2加2，所以他们取得的下标对就完全相同，这时为了避免出现由重复的下标对构成的结果，我们就要加入这个if判断

更新：

关于这里为什么一定要有if判断：是为了防止出现重复使用某个元素，比如p1:[(0,2), (0, 3)], p2:[(2,5), (3, 5)]
关于为什么res一定要用set，是为了去除重复结果，比如：
p1:[(0,2), (1, 5), (3, 5)], p2:[(0, 2), (1, 5), (3, 5)], 此时[nums[0], nums[2], nums[1], nums[5]]和[nums[0], nums[2], nums[3], nums[5]]都为结果, 但nums[1] == nums[3], 即两个结果完全一模一样，所以用set可以去除重复元素。

• 对下表对对应的元素进行排序，将排序后的结果加入到res中。注意，res是set格式，这样可以去除重复元素，set添加元素用的是res.add()

454. 4Sum II

给四个数组，从每个数组中挑一个数字，看有多少个这样的组合相加为0。同样是拆成两个two sum来做

• 用hash table存放前两个数组的two sum
• 用hash table的get()函数找到0-后两个two sum的值，即前两个two sum的和。

dd.get()

dd.get(A[i] + B[j], 0)意思是如果字典里不存在A[i]+B[j]，那就返回0
res += dd.get(0 - C[m] - D[k], 0)
0 - C[m] - D[k] 得到前一个two sum出现的次数，如果他存在，就加进 res, 如果不存在，就加0

• 找到他们在hash里对应的值后，进行叠加，就是最终结果

26. Remove Duplicates from Sorted Array

Time Complexity: O(n)
从数组尾开始，判断是否nums[i] == nums[i-1]，如果是，就删除掉nums[i-1]，del nums[i-1]. 需要注意的是，不管是不是相等，都要i -= 1
不相等的情况比较好理解，相等时，因为删除掉一个元素，数组长度也少了一个，所以i也要减1，才能保持继续指向最后一个元素
如果从数组首端开始，当nums[i] == nums[i+1]时，只需要删除nums[i+1], 不需要移动i。while循环条件要注意：while i < len(nums)-1

27. Remove Element

Time Complexity: O(n)
题目虽然叫remove，但其实并不需要真的删除元素，只是把与target不同值的元素移到list最前边，并返回他们的size。好模糊的题目描述。
用了双指针方法，遇到和target一样的值了，就把左右指针元素交换位置，并将右指针向左移动。否则就将左指针向右移动。
最后返回left就可以
需要注意的是while循环条件中要包含等于：
while left <= right: 针对特殊情况：[1], val = 1

31. Next Permutation

要先理解next permutation是怎么得到的

1. 从后往前找到两个相邻元素，保证后边的元素second大于前边的元素first
2. 将从second开始到末尾的元素排序，即倒置
3. 然后从first之后第一个元素开始查找比first大的元素，找到后将它和first交换位置即可
   reverse函数：

def reverse(self, nums, start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start = start + 1
            end = end - 1

33. Search in Rotated Sorted Array

用了Binary search，运行时间是O(logn)。因为数组在某个点被rotate了，所以可以看成是两个有序数组连在一起。按照binary search的方法先找到mid元素，然后将mid元素和left元素比较，就能发现从left到mid是否为有序，即：if nums[left] <= nums[mid]就为有序，然后可以判断target是否在这个有序序列中，如果在，我们就更新right = mid -1，不在:left = mid +1
如果是后半段有序，（对应上边if语句的else），就判断target是否在后边这个有序序列中，if nums[mid] <= target <= nums[right], 如果在，就更新left，反之更新right
这道题的思路就是比传统二分搜索多了一个判断sorted subarray的条件。

34. Search for a Range

题目要求运行时间控制在O(logn)形式，并且是有序数列，就可以想到要用binary search来做。

• 需要注意的是，while left <= right: 要包含等号，因为有corner case like: [1], target = 1. 这时left = right
• 和普通binary search不同的点就在于当nums[mid] == target时，要向mid的前后延伸，判断nums[mid]前后是否还有等于target的值。因为要返回一个索引范围，所以判断的同时要记录左右范围。

35. Search Insert Position

二分查找的实现，有三点需要注意

• 当nums或者target为空时，返回空
• while left <= right: 要有等号，因为列表里可能只有1个元素存在
• return right + 1 因为while循环结束时，r一定在l左边，此时target不存在数组里，要返回可插入的索引，就是循环结束时r的右边第一个位置，所以是right+1

48. Rotate Image

将一个二维数组顺时针旋转九十度。

• 先将二维数组进行reverse，然后进行两个for循环，外层循环对应行，内层循环对应列，内层循环范围是[i+1, n]，因为reverse之后就对角线上的值就不用动了，每次只需要改变对角线之后的值

56. Merge Intervals

不要默认把interval当作数组类型，要看清题目的定义。
先对intervals以start进行排序，因为是多维列表排序，所以用到了lambda intervals.sort(key = lambda x: x.start)
然后先将第一个interval加入到res中res = [intervals[0]]
针对剩下的每个Interval:
for inter in intervals[1:] if inter.start > res[-1].end: res.append(inter) else: res[-1].end = max(res[-1].end, inter.end)
上一行代码中max的作用是针对：[1, 4], [2, 3]这种情况，即一个interval完全被另一个interval包含

73. Set Matrix Zeroes

follow up要求用constant space，思路是

1. 维护两个变量row_0, col_0，分别用来标记第一行第一列的元素中是否有0存在。
2. 做完标记后，从第二行第二列开始检查，如果有元素为0，就将与该元素对应的第一行，第一列的元素设为0.
3. 检查第一行和第一列的元素，!! 注意是从第一行的第二个元素，和第一列的第二个元素开始检查。因为matrix[0][0]不对应任何内部元素！！！如果第一行有元素为0，就将这列的元素都设为0，如果第一列有元素为0，就将这一行的元素都设为0.
4. 检查row_0和col_0，如果row_0为true, 就说明原始的矩阵，第一行有元素为0，所以应该将第一行元素设为0. 如果col_0为true，就应该将第一列元素设为0

75. Sort Colors

荷兰国旗问题：
http://www.cnblogs.com/gnuhpc/archive/2012/12/21/2828166.html

Paste_Image.png
图片来源：喜刷刷博客