Skip to content

07.Two Pointes.md

Latest commit

 

History

History
160 lines (143 loc) · 12.8 KB

07.Two Pointes.md

File metadata and controls

160 lines (143 loc) · 12.8 KB

第六课：Two Pointes 两根指针

一般适合时间复杂度要求是O（n）的

反向双指针

反向双指针的时间复杂度是O(N)。如果面试官对O(N^2)或者O(NlogN)的解法不满意，或者要求in-place modification, 那就可以考虑双指针方法。 反向双指针的两个应用：1.3-Sum 问题 2.Partition in quick sort or quick select。

  • 0977.Squares_of_a_Sorted_Array.py (E)
    Solution: 反向双指针，找到最大的squares.Trick: we need put value to res from last to start.
  • 0011.Container_With_Most_Water.py (!!M)
    Solution: 反向双指针，i, j分别为（0，n-1）舍弃更小的height.
  • 0042.Trapping_Rain_Water.py (!!H)
    Solution1:bruce force For column_i, the rain it can trap: r[i] = min(max(h[0i]), max(h[in-1])) - h[i] ans = sum(r[i]) 时间：o(n^2) 空间：o(1) Solution2:DP Solution3:two pointer 解析: 山景城一姐de讲解：首先找到最高highestBar的位置。然后从左边往最高的位置扫，同时maintain一个指针记录leftHighest的高度，如果扫到的地方i小于这个leftHighest的高度，则说明i这个地方可以蓄水，可蓄水量为leftHighest的高度减去i的高度；如果扫到的地方i大于这个leftHighest的高度，则说明i这个地方不可以蓄水，因为水会从左边溜走，所以这时候要更新leftHighest为i的高度。同理对右边做同样的操作.O(N), O(1). 九章：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
  • 0415.Valid_Palindrome.py (Lintcode M)

注意：partition相关都写成 l <= r

  • 0031.Partition Array （LintCode）
    Solution:注意：4个地方的判断语序写成一样的，一定是<=.
  • 0075.Sort Colors Sort Colors 三分的问题
    解法：将数组分成两个部分 vs 分成三个部分 1)2次partition，先分0和1-2，再分1-2 2)只能1次循环, 用3个index标记，left，index，right。left的左边都为0，right的右边都为2.
  • 0905.Sort_Array_By_Parity.py （M）
    solution 1: 同向双指针； solution 2: 反向双指针 - partition 好像两种方法都不能maintain the original order of numbers. 貌似同向双指针可以maintain the original order of numbers.
  • 0912.Sort an Array
    Solution: quick sort:基本思想是partition，记住partition模板，就可以记住quick sort. merge sort:分治，先求出[:mid][mid:n]的两个递增数组，然后合并，合并时采用同向双指针合并。
  • [1237.Find_Positive_Integer_Solution_for_a_Given_Equation.py](Solutions/ 1237.Find_Positive_Integer_Solution_for_a_Given_Equation.py) （M）
    solution1: 反向双指针.solution2:binary search
Summary:
Two sum // three sum // four sum 
Solution 1: brute force                                                 O(N**2)  O(1)
Solution 2: hash  sort/unsort both ok,                                  O(n), O(n)
Solution 3: two pointer sort: O(n), unsort: we need sort first O(nlogn) O(nlogn) // O(n), O(1)
Two pointer while condition:  while(i < j)
keep mind: some question, we need remove repeat element.

three sum：two point 
brute force:  o(n**3) o(1)
hash:         o(n**2) o(n)
two pointer:  o(n**2 + nlogn)//o(n**2) o(1)     更适合

关于去重：
solution 1:过程中去重
i if i > 0 and nums[i] == nums[i - 1]: continue
j if j > i + 1 and nums[j] == nums[j - 1]: continue
k and m :
if four_sum == target:
    res.append([nums[i], nums[j], nums[k], nums[m]])
    k += 1      #要先加减之后再比较去重
    m -= 1
    while k < m and nums[k] == nums[k - 1]:
        k += 1
    while k < m and nums[m] == nums[m + 1]:
        m -= 1
solution 2: 对结果去重
res = set()  直接return res

1.Two Sum

模板必记：可以循环其中一个变量，然后研究另外一个变量如何变化
1.哈希表(HashMap)，判断target-num在不在hashmap中，在的话，return true.适用于没排序。
2.两根指针(Two Pointers)，先排序，一个指针从前往后走，一个指针从后往前走。 3.如果没有说数组有没有重复，一定要记得去重。

  • 0001.Two Sum(!!E)
    Solution: array没有排好序，不重复。对于求2个变量如何组合的问题可以循环其中一个变量，然后研究另外一个变量如何变化.普世的方法是：for循环一个变量a，然后看另外一个变量target-a是不是在一个hashmap中。method: a.hashmap 存<nums[i], i> b.先排序[需要保存index] 低空间复杂度 two pointers
  • 0167.Two Sum II Input Array Is Sorted (E)
    Solution: array排好序，不重复。使用Two Pointers更好, 且不需要额外的存储空间。O（T） = O（N）
  • 0170.Two_Sum_III_Data_structure_design (E)
    Solution: array求存不存在, 注意可能有重复。Data structure design 只能使用HashMap，数组大小固定不能添加新元素，所以不能用2根指针
  • 0653.Two_Sum_IV-Input_is_a_BST.java (E)
    Solution 1: 注意输入是BST，in-order是从大到小，所以可以用2个指针.First, we need use inorder to get inorder array. Then user two point to solve the problem. Solution 2: hash, 一边遍历一边check，target - val是否在set中.
  • 1214.Two_Sum_BSTs.py (M)
    Solution: Iteratively do an inorder traversal for root1, and store the val in a hashSet; then itteratively do an inorder traversal for root2, and at the same time check if a target-val is in the hashSet. time complexity: O(M + N). 算法跟two sum是一样的，如果闭着眼睛能写要会iterative in-order traversal的哈！1. hashset, 一边遍历一个array，一遍存入hashset中，然后遍历另一个array，一遍判断存不存在 2. in-order-traversal + 反向双指针：分别中序遍历2个array，然后反向双指针去判断。 3. brutal force。
  • 1099.Two_Sum_Less_Than_K.py (E)
    Solution:小于K只能用双指针，记得先排序。
  • 0609.Two_Sum-Less_than_or_equal_to_target.py (!!E Lintcode)
    Solution:类似1099题，不同在于要记录pair的个数
  • 0043.Two_Sum-Greater_than_target.py (!!E Lintcode)
  • 0533.Two Sum - Closest to target (lintcode)
    Two Sum Closest. Solution:类似609题，只是要记录距离target最接近的。大于或者小于都可以。
  • 0587.Two_Sum-Unique_pairs.py (!!M Lintcode)
    Solution:找unique pair which sum equal to target. Unique pairs 是否可以先去重？不能. So we need record the last position. when sum is equal to target, we need check if the pos is equal to last pos, if it is same, skip it.
  • 0012.Two_Sum-Difference_equals_to_target.py (lintcode)
    Sulotion: 只能同向双指针做
  • 1010.Pairs_of_Songs_With_Total_Durations_Divisible_by_60.py (M)
    nums = [time % 60 for time in times]; Now it's a two sum problem with target = 60

2. 3 Sum & 4 Sum

  • 0015.3Sum (!!M)
    Solution 1: two pointer, fix one value, then do the 2 sum. Attention:remove duplicate when we do sum. 固定的num去重，2-sum时去重。 Solution 2: hashset
  • 0016.3Sum Closest (M)
    Solution: same as 15, fix one value. attention: check how to move point.
  • 0259.3Sum_Smaller.py (M)
    Solution: since we need find 3 sum, which is smaller than target. we donot need to check one by one. fix one val, then check 3sum, if num[i] + num[l] + num[r] < target means num[i] + num[l] + num[r-1] also < target. next we just need to change i. Attention: time limit.
  • 0018.4Sum.py (M)
    Solution 1: O(N^3): 3Sum模板双指针法。注意这里给j去重不能从j>=1开始，因为要至少让j先取上第一个值i+1之后才能与前一个数比较！不然[0,0,0,0], 0就通不过了；solution 2: O(N^2): hashmap. for循环a, b,保存a+b的值进hashmap, 再for循环c, d, 判断c+d是否在hashmap中.
  • 0454.4Sum_II.py (M)
    Solution: num1[] num2[] num3[] num4[] find tuple count.
  • 0089.k_Sum.py (M)
    Solution:要求从一些正整数中选出一些，使得和是Target.背包问题.数组A：各个物品的重量.Target：背包最大称重.使得和是Target：背包正好装满.最后一步：最后一个数An-1是否选入这K个数.情况一（An-1不选入）：需要在前n-1个数中选K个数，使得它们的和是Target. 情况二（An-1选入）：需要在前n-1个数中选K-1个数，使得它们的和是Target - An-1.要知道还有几个数可选，以及它们的和需要是多少：序列加状态. 状态：f[i][j][s]表示有多少种方法可以在前i个数中选出j个，使得它们的和是s f[i][j][s] = f[i-1][j][s]; if s>=A[i-1]: f[i][j][s] += f[i-1][k-1][s-A[i-1]].
  • 0090.k_Sum_II.py (M) (lintcode)
    使用backtrack

注意：只求个数可以用DP做，如果要求全部result就不能用DP.用backtrack或者递归

3.partition

partition 操作注意记住写着：4个地方的 l<=r

4.quick sort + merge sort

partition 操作注意记住写着l<=r

  • 0912.Sort an Array
    Solution: quick sort:基本思想是partition，记住partition模板，就可以记住quick sort. merge sort:分治，先求出[:mid][mid:n]的两个递增数组，然后合并，合并时采用同向双指针合并。
  • 0215.Kth_Largest_Element_in_an_Array
    solution 1: heapq, time: O(N+KlogK), N 来自于for循环，logK来自于heap的长度是K，heap 的push 和pop都是logK; heapq适合做第K大，第K小，前K大，前K小问题; solution 2: quick select: O(N) - O(N^2). solution 3: bucket sort O(N). use frequency as idx to store number.
  • 0169.Majority_Element
    select sort

同向双指针