Post

Algorithm Notes: Intro And Two Pointers

Jan 1, 2021·40 min read·#Algorithm Notes #Study Notes

Algorithm Notes

LintCode Ladder / Notes

Chapter 1: Intro

[627 Longest Palindrome]
[13 Implement strStr()]
415 Valid Palindrome
[200 Longest Palindromic Substring]
1790 Rotate String II
[667 Longest Palindromic Subsequence]
[841 String Replace]
594 strStrII

Chapter 2: 复杂度理论与双指针算法入门

228 Middle of Linked List
607 Two Sum III - Data structure design
559 Move Zeros
521 Remove Duplicate Numbers in Array
464 Sort Integers II
143 Sort Colors II
57 3Sum
31 Partition Array
5 Kth Largest Element
[1343 Sum of Two Strings]
[1276 Sum of Two Integers]
[1143 Minimum Index Sum of Two Lists]
604 Window Sum
56 Two Sum
[1604 Maximum Sum of Two Numbers]
1375 Substring With At Least K Distinct Characters
[1076 Minimum ASCII Delete Sum for Two Strings]
[689 Two Sum IV - Input is a BST]
608 Two Sum II - Input array is sorted
610 Two Sum - Difference equals to target
609 Two Sum - Less than or equal to target
587 Two Sum - Unique pairs
533 Two Sum - Closet to target
443 Two Sum - Greater than target
461 Kth Smallest Numbers in Unsorted Array
382 Triangle Count
148 Sort Colors
59 3Sum Closest
[1879 Two Sum VII]
[465 Kth Smallest Sum in Two Sorted Arrays]
[894 Pancake Sorting]
625 Partition Array II
380 Intersection of Two Linked Lists
102 Link List Cycle
58 4Sum
103 Linked List Cycle II
1343 Sum of Two Strings

补充：

1.1 复杂度

时间复杂度：

P 问题：(Polynomial)

指可以被多项式描述复杂度的问题。比如：O(n), O(n^2), O(n + m), O（sqrt（n））， O（nlogn）， O（logn）此类。

NP 问题：(Nondeterministic Polynomial)

指不能被多项式描述复杂度的问题，或者尚为发现可被多项式描述的算法。比如：O（2^n), O(n^n), O(n!

时间复杂度只考虑最高项，不考虑常数项和系数项

Example: O(log(N^2)) ==> O(2logN) ==> O(logN)

再比如此题：

a = 0
for i in range(1, n):
	for j in range(1,n/i):
		a += 1

T(n) = n + n/2 + n/3 + n/4 + ... + n/n，而根据数学知识，这一部分求和的结果的下界是nln(n)。因此时间复杂度是O(nlogn)级别的。

时间复杂度为O（N）的算法：

双指针算法
打擂台算法
单调栈算法
单调队列算法
etc ...

1.2 双指针算法

双指针的类型：

背向双指针：
1. 中心线枚举，比如 Longest Palindromic Substring
2. 二分法，find K Closet Elements
相向双指针：
1. Reverse 型
2. Two Sum 型
3. Partition 型
同向双指针：
1. 滑动窗口类 sliding window
2. 快慢指针类 Fast & Slow Poionters

1.3 相向双指针:

Reverse 型：
- 翻转字符串
- 判断回文串

Two Sum 型态：
- 两数之和
- 三数之和

Partition 型：
- 快速排序
- 颜色排序

例题1： Valid Palindrome

class Solution:
    def isPalindrome(self, s):
        left, right  = 0, len(s) - 1
        while left < right:
            
            ### 分别从左往右先找出去掉标点等是字母或数字的字符，更新left和right的指针。
            while left < right and not self.isValid(s[left]):
                left += 1
            while left < right and not self.isValid(s[right]):
                right -= 1
                
            ### 判断现在left和right是否满足palindrome的边界
            ### 此处注意细节，要再判断以下更新后的left和right是否越界！
            if left < right and s[left].lower() != s[right].lower():
                return False
            
            left += 1
            right -= 1
        
        return True
  
            
    def isValid(self, char):
        return char.isdigit() or char.isalpha()

例题2： Valid Palindrome II

class Solution:
    def validPalindrome(self, s):
        if not s:
            return False
        
        ### 先找到不一样的left和right在哪
        left, right = self.find_ptrs(s, 0, len(s) - 1)
       
        ### 如果筛出来的left和right相等，证明不存在不相等的字符，所以直接return True
        if left == right:
            return True
        else:
            ### 如果找到了不相等的字符的位置，分清况讨论，这里用一个子函数封装了一下：
            return self.isPalindrome(s, left + 1, right) or self.isPalindrome(s, left, right - 1)
        
    ### 此处注意这两个子函数设计的时候， 要避免代码重复，所以需要机智的利用返回指针和判断指针位置的方法。
    ### 不要写成使用两次双指针代码相同，但却不把逻辑封装。
    def find_ptrs(self, s, left, right):
        while left < right :
            if s[left] != s[right]:
                return left, right     
            left += 1
            right -= 1
        return left, right
    
    def isPalindrome(self, s, left, right):
        res_left, res_right = self.find_ptrs(s, left, right)
        return res_left >= res_right

例题3：Two Sum & Two Sum II - Input Array is sorted

Solution 1: 哈希表的做法 (T: O(n), S: O(n))

class Solution:
    def twoSum(self, nums, target):
        hashmap = {}
        for i, v in enumerate(nums):
            ### 先检测
            if target - v in hashmap:
                return hashmap[target - v], i   
            ### 再添加   
            hashmap[v] = i

Solution 2: 相向型双指针的做法: (T:O(nlogn), S:O(n))

特点是需要先排序。如果如例题一样返回下标，Space的复杂度其实是O(n) 而不是 O(1), 因为要开一个数组包括index来排序。如果只是需要返回原数字，不需要返回下标，那么Space复杂度是O(1), 不需要额外空间如另一道例题Two Sum II - Input Array is sorted。

class Solution:
    def twoSum(self, numbers, target):
        if not numbers:
            return [-1, -1]
        
        ### 这里有个小技巧，利用tuple来带上原来的index对num进行排序。
        nums = [(number, index) for index, number in enumerate(numbers)]
        ### 先排序
        nums.sort()
        ### 双指针
        left, right = 0, len(nums) - 1
        while left < right:
            ### 因为数组已经从小到大排过序了
            ### 如果左+右 比 target 大， 那么说明右过大，需要把右指针左移
            if nums[left][0] + nums[right][0] > target:
                right -= 1
            ### 如果左+右 比 target 小， 那么说明左过小，需要把左指针右移
            elif nums[left][0] + nums[right][0] < target:
                left += 1
            else:  
                ### 如果相等
                return sorted([nums[left][1], nums[right][1]])    
        return [-1, -1]

例题4：Two Sum - Less than or equal to target

Similar Problem: LeetCode-1099 Two Sum Less Than K

class Solution:
    """
    @param nums: an array of integer
    @param target: an integer
    @return: an integer
    """
    def twoSum5(self, A, K):
        # write your code here
        if not A:
            return 0
        A.sort()
 
        res = 0
        left, right = 0, len(A) - 1
        while left < right:
            if A[left] + A[right] > K:
                right -= 1
            else:
                ### 这里计算以下当前left符合条件的可能性应该是right-left个。
                res += right - left
                ### 再更新left指针。
                left += 1
        return res

1.4 同向双指针:

两根指针都从头出发，朝着同一个方向移动。两根指针同向而行，都不会“回头”，每个指针访问数组中每个元素最多一次。所以复杂度是 O(n) 。

例题1 :610 Two Sum - Difference equals to target

此题的普通解为hashmap O（N）或者是 Binary Search O（nlogn）。

最优解应该是同向双指针。因为求的是差，那么i右移，j也右移动（假设是有序的数组），那么我们其实可以用同向双指针。

那么这道题为什么不能用相向双指针来做呢？

在两数之和（Two Sum) 这道题中。假设数组是有序的，从大到小，那么对于相向双指针来说，L右移，R不变，保证判断条件的SUM变大。而L不变，R左移动，保证判断条件的SUM变小。所以指针的移动对应着不同的条件所以是可以用相向的。那么此时搜索范围是可以缩短的。

然而这道题两数之差，如果相向的话，L右移，R不变，判断条件的Diff变小。而L不变，R左移动，保证判断条件的Diff变小。指针相向的移动并没有对应不同的判断条件，所以并没有起到缩小搜索范围的效果，所以不能使用相向的双指针，那么则应该考虑的是使用同向的双指针，并判断，如果同向的移动是不是会起到缩小范围的效果。

class Solution:
    """
    @param nums: an array of Integer
    @param target: an integer
    @return: [num1, num2] (num1 < num2)
    """
    def twoSum7(self, nums, target):
        if not nums:
            return [-1, -1]
            
        target = abs(target)
        j = 1
        for i in range(len(nums)):
            ### 此操作避免i=j
            j = max(j, i + 1)
            while j < len(nums) and nums[j] - nums[i] < target:
                j += 1
            if j >= len(nums):
                break
            if nums[j] - nums[i] == target:
                return [nums[i], nums[j]]
                
        return [-1, -1]

同向双指针的模板：

j = 1
for i from 0 to n - 1:
    ### 有些题目需要使得i，j不能相同
    ### 那么：
    ### j = max(j, i + 1)
    while j < n and i, j 的搭配不满足条件
        j += 1
    if j >= n
        break
    处理 i，j 这次搭配

例题2 :1870 number of substrings with all zeroes

利用同向双指针来找符合条件的区间。

详解，利用同向双指针来找区间

class Solution:
    """
    @param str: the string
    @return: the number of substrings 
    """
    def stringCount(self, str):
        # Write your code here.
        
        if not str:
            return 0
        
        ### 这道题利用同向双指针
        ### i 为 0000 的首
        ### j 为 00001 的 1 的位置，即全零子串的结尾的下一位非0的位置
        
        ### 每次对i iterate 以后，找到结束的j，那么计数器加上 j - 1
        ### 这样就能出这段全零子串的组合数。
        ### 比如：
        ### 1 0 0 0 1 2 
        ### i j
        ###   i j
        ###   i   j
        ###   i     j
        ###   res += j - i = 4 - 1 = 3
        ###     i j
        ###     i   j
        ###   res += j - i = 3 + 4 - 2 = 3 + 2 = 5
        ###       i j
        ###   res += j - i = 5 + 4 - 3 = 5 + 1 = 6
        ###         i j
        ###           i j (out of bound, end)
 
        n = len(str)
        res = 0
        j = 1
        for i in range(n):
            if str[i] != '0':
                continue
            j = max(j, i + 1)
            while j < n and str[j] == '0':
                j += 1
            
            res += j - i
        
        return res

同向双指针之滑动窗口问题

例题 1. 604 Window Sum

class Solution:
    """
    @param nums: a list of integers.
    @param k: length of window.
    @return: the sum of the element inside the window at each moving.
    """
    def winSum(self, nums, k):
        # write your code here
        if not nums or len(nums) < k:
            return []
            
        result = []
        j = 0
        window_sum = 0
        for i in range(len(nums)):
            while j < len(nums) and j - i < k:
                window_sum += nums[j]
                j += 1
            if j - i == k:
                result.append(window_sum)
            
            ### 在iterate 之前，从窗口中剪掉之前的第一个数
            window_sum -= nums[i]
        
        return result

例题 2. 1246 Longest Repeating Character Replacement

超经典的sliding window题目，需要好好理解。

sliding window的特点就是，找到跳出window的条件，一般来说与j指针的最大最小位置有关。

进入窗口要更新窗口的计数器。

slide窗口之前要把窗口里最早的数拿掉，并且更新计数器，和其他相关的参数。

class Solution:
    def characterReplacement(self, s, k):
        ### 同向双指针 sliding window类型经典题目
        if not s:
            return 0
        ### 选择j和i在0，0 起点
        j = 0
        ### 用maxFreq来记录，并且计算窗口中需要replace的少数characters, 这里一定是多数会成为maxFreq，然后去替换少数。
        maxFreq = 0
        
        ### 用dict来maintain window里的计数
        counter = {}
        
        
        res = 0
        for i in range(len(s)):
            
            ### 这里若 j < len(s) 则不会执行了，而j是不断递增地，所以overall，O（N）的复杂度，不是O（n^2） 
            ### 退出条件，如果 j - i - maxFreq <= k, 这里一定是小于等于
            ### j - i 是目前的长度，减去maxFreq那么则是 需要被替换的个数
            while j < len(s) and j - i - maxFreq <= k:
                ### 记录j上的数，放进计数器更新
                counter[s[j]] = counter.get(s[j], 0) + 1
                ### 同时查看新进入window的数 freq是否超过maxFreq，更新
                maxFreq = max(maxFreq, counter[s[j]])
                ### 右移动j指针
                j += 1
            ### 如果跳出了循环，那么check j - i - maxFreq 与k的关系
            if j - i - maxFreq > k:
                ### 大于 k，此时的j之前的一位 j - 1 是没跳出循环前满足条件的位置，那么 j - 1 - i 就是符合条件的长度
                res = max(res, j - i - 1)
            else:
                ### 如果是别的情况，比如是j越界了，但是k还是满足的，那么说明现在位置j仍然满足条件，目前的窗口长度就是j - i
                res = max(res, j - i)
            ### 在iterate 下一个 i 之前，在counter里剪掉 i上的数
            counter[s[i]] -= 1
            ### 不要忘了修改counter以后需要更新maxFreq，这里虽然用了遍历counter.values() 的方式，实际上这个list的key是有限的，因为是按字母存的，可以认为对时间复杂度没有影响。
            maxFreq = max(counter.values())
        
        return res

同向双指针解决链表问题快慢指针

例如用快慢双指针解决链表的中点问题。

可能的想法是：

先遍历一下整个链表，求出长度 L，然后再遍历一下链表找到第 L/2 的那个位置的节点。

但是在你抛出这个想法之后，Follow up 如果只允许遍历链表一次怎么办？

可以看到这种 Follow up 并不是让你优化算法的时间复杂度，而是严格的限制了你遍历整个链表的次数。你可能会认为，这种优化有意义么？事实上是很有意义的。因为遍历一次这种场景，在真实的工程环境中会经常遇到，也就是我们常说的数据流问题（Data Stream Problem）。

数据流问题 Data Stream Problem 所谓的数据流问题，就是说，你需要设计一个在线系统，这个系统不断的接受一些数据，并维护这些数据的一些信息。比如这个问题就是在数据流中维护中点在哪儿。（维护中点的意思就是提供一个接口，来获取中点）

类似的一些数据流问题还有：

数据流中位数 http://www.lintcode.com/problem/data-stream-median/

数据流最大 K 项 http://www.lintcode.com/problem/top-k-largest-numbers-ii/

数据流高频 K 项 http://www.lintcode.com/problem/top-k-frequent-words-ii/

这类问题的特点都是，你没有机会第二次遍历所有数据。

用双指针算法解决链表中点问题

我们可以使用双指针算法来解决链表中点的问题，更具体的，我们可以称之为快慢指针算法。

 
slow, fast = head, head.next
while fast != None and fast.next != None:
    slow = slow.next
    fast = fast.next.next
return slow

在上面的程序中，快指针放在了第二个节点上，慢指针放在了第一个节点上，while循环中每一次快指针走两步，慢指针走一步，这样当快指针走到头的时候，慢指针就走到中点了。

102 Linked List Cycle

另一个很典型的例子是带环链表问题。

 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def hasCycle(self, head):
     
        # write your code here
        slow = head
        if slow is None:
            return False
        fast = head.next
        if fast is None:
            return False
        
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        
        return False

103 Linked List Cycle II

这道题是linked list cycle的基础上，要再求环的入口。方法是当快慢指针相遇后，从头移动慢指针，两指针再次相遇之处就是环的入口。

找环的入口Node的方法。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def detectCycle(self, head):
        # write your code here
        if head == None or head.next == None:
            return None
        
        slow, fast = head, head.next ### 初始化快慢指针
        
        while fast != slow: ### 直到两指针相遇
            if fast is None or fast.next is None:
                return None
            fast = fast.next.next
            slow = slow.next
        
        while head != slow.next: ### 快慢相遇后，看head 和 slow.next的相遇，并各自速度为1步更新，直到相遇时的head就是入口。
            head = head.next
            slow = slow.next
            
        return head

380 Intersection of Two Linked Lists

带环链表，找环入口的又一次引申。这道题的做法在于，现将两个List构成一个环（其中一条首尾相连即可），那么交点就是要求的，就转换成了找环的入口的题目了。

构造环，然后再找入口为intersection的方法。此方法会修改原来的LinkedList。

class Solution:
    """
    @param headA: the first list
    @param headB: the second list
    @return: a ListNode
    """
    def getIntersectionNode(self, headA, headB):
        # write your code here
        
        if headA == None or headB == None:
            return None
        
        connect = headA
        while connect.next != None:
            connect = connect.next
        connect.next = headA
        
        head = headB
        slow, fast = head, head.next ### 初始化快慢指针
        
        while fast != slow: ### 直到两指针相遇
            if fast is None or fast.next is None:
                return None
            fast = fast.next.next
            slow = slow.next
        
        findIntersection = head
        while findIntersection != slow.next: ### 快慢相遇后，看head 和 slow.next的相遇，并各自速度为1步更新，直到相遇时的head就是入口。
            findIntersection = findIntersection.next
            slow = slow.next
            
        return findIntersection

不modify原来链表的方法，双指针。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
 
class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        if headA is None or headB is None:
            return None
 
        pa = headA # 2 pointers
        pb = headB
 
        while pa is not pb:
            # if either pointer hits the end, switch head and continue the second traversal, 
            # if not hit the end, just move on to next
            pa = headB if pa is None else pa.next
            pb = headA if pb is None else pb.next
 
        return pa # only 2 ways to get out of the loop, they meet or the both hit the end=None
 
# the idea is if you switch head, the possible difference between length would be countered. 
# On the second traversal, they either hit or miss. 
# if they meet, pa or pb would be the node we are looking for, 
# if they didn't meet, they will hit the end at the same iteration, pa == pb == None, return either one of them is the same,None

Chapter 2: 排序算法

分治法概念的排序算法。

2.1 Quicksort

Quicksort平均时间复杂度是O(nlogn), 最坏情况的时间复杂度可以到 O（n^2)

Quicksort一般使用递归处理，要注意左右指针的边界判断条件带不带等于号，不然很容易造成stackoverflow。

例题：464 Sort Integers II

Similar Problem: LeetCode-912 Sort an Array

463 Sort Intergers

Quicksort Solution

class Solution:
    def sortArray(self, A):
        if not A:
            return
        self.quicksort(A, 0, len(A) - 1)
        return A
        
    
    def quicksort(self, A, start, end):
        
        ### recursion ending condition
        if start >= end:
            return
        
        ### denote left and right pointers
        left, right = start, end
        ### identify pivot, here choose pivot as the whole array's middle index's value
        pivot = A[int((start + end) / 2)]
        
        ### advancing the left, right ptrs, until we find the two numbers needed to be swapped
        '''
        1. 这里注意一定是left <= right 作为while loop的条件。因为我们需要避免left 和 right 重叠。这是因为quicksort是recursion， 下一步的时候必须保证
        分出的两个部分不能有交集(如果有交集会造成stackoverflow)，所以要在left = right的时候，对left， right也进行一次符合排序逻辑的操作，使得left 和 right不相等，而且可以退出循环。
        2. 同时与pivot的比较的时候，不要包括等于的情况，也会造成stack overflow 你如【1， 1， 1， 1， 1】 这种情况left会一直加到left>right, 造成right没有条件变小。
        导致sort的数组size并没有变化而一直在递归，会stackoverflow。
 
        '''
        while left <= right:
            while left <= right and A[left] < pivot:
                left += 1
            while left <= right and A[right] > pivot:
                right -= 1 
            ### after found the left, and right, needed to be swamped, here swap them and then advance the left and right ptrs, 
            ### continue to check others and swap, and then continue until out the loop
            if left <= right :
                temp = A[left]
                A[left] = A[right]
                A[right] = temp
                left += 1
                right -= 1
        ### Now we have just divided the A using the pivot value into two parts, 
        ### start to right and left to end. As now left should be larger than right, but they are nor overlapped, 
        ### since we take care of while loop condition.
        self.quicksort(A, start, right)
        self.quicksort(A, left, end)
        ### we perform the quicksort on both parts.
        ### The ending condition will be the inputs for quicksort new start and end, 
        ### start is larger or equal to end, then we came to the end of the sort.

2.2 Mergesort

Mergesort平均时间复杂度是O(nlogn), 最坏情况的时间复杂度也是 O（nlogn)。

Mergesort 是必须耗费空间的。需要新开一个数组如合并。虽然mergesort是 O(nlogn), quicksort 是O(nlogn) ~ O(n^2), 但多数情况下quicksort更快，因为他不需要额外空间。

例题：464 Sort Integers II 我们用和quicksort同样的例题来做。

Mergesort Solution

class Solution:
    def sortArray(self, A):
        if not A:
            return
        ### 需要新建一个同样大小的数组。
        temp = [None] * len(A)
        self.mergeSort(A, 0, len(A) - 1, temp)
        
        ### 利用temp对A作改变，最后A应该被temp swap了。所以返回A
        return A
        
    
    def mergeSort(self, A, start, end, temp):
        ### recursion ending condition:
        if start >= end:
            return
        ### 分治法
        middle = int((start + end) / 2 )
        self.mergeSort(A, start, middle, temp)
        self.mergeSort(A, middle + 1, end, temp)
        ### merge
        ### 这个merge算法非常经典，需要熟练掌握。
        self.merge(A, start, end, temp)
     
    def merge(self, A, start, end, temp):
        middle = int((start + end) / 2)
        ptr1 = start
        ptr2 = middle + 1
        
        ### 这里一定要预留出来temp的index是从start开始操作的。
        temp_index = ptr1
        
        ### 注意这里不能用append因为我们一直对temp操作，要操作到index上。append只会添加到temp的结尾，并不能改变temp。
        ### 所以赋值要用while loop
        while ptr1 <= middle and ptr2 <= end:
            if A[ptr1] < A[ptr2]:
                temp[temp_index] = A[ptr1]
                ptr1 += 1
                temp_index += 1
            else:
                temp[temp_index] = A[ptr2]
                ptr2 += 1
                temp_index += 1
        
        ### check if ptr1 still <= middle or ptr2 still <= end:
        while ptr1 <= middle:
            temp[temp_index] = A[ptr1]
            temp_index += 1
            ptr1 += 1
        while ptr2 <= end:
            temp[temp_index] = A[ptr2]
            temp_index += 1
            ptr2 += 1
        ### 此处记得一定要在merge的时候，讲temp里的值一个一个赋值回去到A
        for i in range(start, end + 1):
            A[i] = temp[i]

2.3 QuickSort VS MergeSort:

Time Complexity:

QuickSort Average Time Complexity is O(nlogn), worst case is O(n^2)
MergeSort Average Time COmplexity is O(nlogn), worst case is also O(nlogn)

Space Complexity:

QuickSort: In-Place O(1)
MergeSort: extra space O(n)

Stability:

QuickSort : Unstable, cant gurantee, outputs are always the same, say [1 1' 2 2'] may be [1' 1 2 2'] ... when equal condition meets
MergeSort : Stable

QuickSort：先整体有序，再局部调整的算法

MergeSort：先局部有序，在整体合并的算法

两种算法时间复杂度表示的分治法来看： T(n) = 2 T(n/2) + O(n)，很显然，MergeSort先进性的局部有序 2 T(n/2) 的操作，然后全局合并O(n) 的操作。而QuickSort则是现进行的全局排序O(n) (和pivot作对比，大小归类)，然后再进行的是对局部的排序 2 T(n/2) 的操作。

2.4 QuickSelect

利用QuickSort的思想。找出K大值或者median问题这些数，所在的区间，这样就缩小了范围，只需要对该区间进行排序。 T（n） = O(n) + T（n/2）= O（n） + O(n/2) + O(n/4) + ... = O(n)

例题：5 Kth Largest Elerment in an Array

解法：

O(nlogn) --> sort
O(n) --> quickselect based on quicksort

Similar Problem:

461 Kth Smallest Numbers in Unsorted Array We calculate the K largest using by converting to find the K smallest first. Remember rank = idx + 1.

65 Median of Two Sorted Arrays

QuickSelect Solution

class Solution:
    def findKthLargest(self, nums, k):
        
        if not nums:
            return -1
        
        ### Change this kth large to kth small, so it is easy to index, as the sorting order is ascending. 
        n = len(nums)
        k = n - k
        
        ### Start the recursion "quickselect"
        ### Based on the quicksort method
        return self.quickselect(nums, 0, len(nums) - 1, k)
        
    
    def quickselect(self, nums, start, end, k):
        
        ### if start =  end, then it is kth smallest we are looking for, 
        ### as K is always within the [start, end] range
        if start == end:
            return nums[k]
        
        ### deploy quicksort methodology
        left, right = start, end
        middle = int((left + right) / 2)
        pivot = nums[middle]
        
        while left <= right:
            while left <= right and nums[left] < pivot:
                left += 1
            while left <= right and nums[right] > pivot:
                right -= 1
            ### swap and narrow down
            if left <= right:
                temp = nums[left]
                nums[left] = nums[right]
                nums[right] = temp
                left += 1
                right -= 1
            
        ### after swapping, we should have the following:
        ### [start ... right (...) left ... end]
        ###         ^          ^         ^
        ### There are only three locations where k can be
        ### And if k is within right , left, k is found, as per the logic, 
        ### left and right swapped when they are equal, and left += 1, right -= 1, when there is one element inside. 
        ### or left larger than right, and between left and right, there is no element. 
        if k <= right:
            return self.quickselect(nums, start, right, k)
        if k >= left:
            return self.quickselect(nums, left, end, k)
        
        return nums[k]

练习题

148 Sort Colors

此题可以通过partition的方法一0， 1 分别作pivot，两次scan完成, Space O(1) 。或者是通过counting sort的方法，也是两次scan完成。都是O（n）解, Space O(n)。

普通解：两次扫描，双指针quicksort优化版

class Solution:
    def sortColors(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        left, right = 0, len(nums) - 1
        new_left = self.partition(nums, left, right, 0)
        self.partition(nums, new_left, right, 1)
                
    def partition(self, nums, left, right, pivot):
        while left <= right:
            while left <= right and nums[right] != pivot:
                right -= 1
            while left <= right and nums[left] == pivot:
                left += 1
            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        return left

最优解：基于双指针的三指针 One Pass （一次扫描 O(n)) 最优解

class Solution:
    def sortColors(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        # for all idx < p0 : nums[idx < p0] = 0
        # curr is an index of element under consideration
 
        ### p0 : ptr to zeros,
        ### p2 : ptr to twos
        ### curr : should be ptr on ones
 
        ### the move on p0 and p2 depends on curr's value
 
        p0 = curr = 0
        # for all idx > p2 : nums[idx > p2] = 2
        p2 = len(nums) - 1
 
        while curr <= p2:
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1

65 Median of Two Sorted Arrays

此题简单解法就是mergeSort的中merge的方法讲两个array merge然后取中点。这样需要O(n + m), 或者是直接想成k大k小问题，用quickselect直接套用O(log(n+m)) quick select 应该针对的是无序数组，有一个partition 的过程，这里没有，仅仅是通过二分。

普通解：转化成FindKth问题

class Solution:
    """
    @param A: An integer array.
    @param B: An integer array.
    @return: a double whose format is *.5 or *.0
    """
    def findMedianSortedArrays(self, A, B):
        n = len(A) + len(B)
        if n % 2 == 1:
            return self.findKth(A, 0, B, 0, n // 2 + 1)
        else:
            smaller = self.findKth(A, 0, B, 0, n // 2)
            bigger = self.findKth(A, 0, B, 0, n // 2 + 1)
            return (smaller + bigger) / 2
 
    def findKth(self, A, index_a, B, index_b, k):
        if len(A) == index_a:
            return B[index_b  + k - 1]
        if len(B) == index_b:
            return A[index_a + k - 1]
        if k == 1:
            return min(A[index_a], B[index_b])
        
        a = A[index_a + k // 2 - 1] if index_a + k // 2 <= len(A) else None
        b = B[index_b + k // 2 - 1] if index_b + k // 2 <= len(B) else None
        
        if b is None or (a is not None and a < b):
            return self.findKth(A, index_a + k // 2, B, index_b, k - k // 2)
        return self.findKth(A, index_a, B, index_b + k // 2, k - k // 2)

但是存在更好的解法，通过binary search，有点类似bitonic sequence的感觉，只需要O（log min(m, n)）就能通过寻找两个array 各自partition的位置，来找到中点。

left_part	right_part
`A[0], A[1], ..., A[i-1]`	`A[i], A[i+1], ..., A[m-1]`
`B[0], B[1], ..., B[j-1]`	`B[j], B[j+1], ..., B[n-1]`

We need to find maxLeft A <= minRight B, and maxLeft Y <= minRight X, 需要找到符合条件的i，通过对较短的一个array进行满足此条件的binary search

参考：

https://www.jiuzhang.com/solution/median-of-two-sorted-arrays/#tag-highlight-lang-java

https://www.youtube.com/watch?v=do7ibYtv5nk

https://www.youtube.com/watch?v=KB9IcSCDQ9k

最优解：基于寻找Binary Search， search partition的方法。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        #get overall sense:
        a = len(nums1)
        b = len(nums2)
        length = a+b
        # found the total size of the "merged" array
        # now define them short, long, based on their length
        # notice that:
        # short and long will contribute a portion to the merged array left side before the median, we need to find out the location that happend in short, and long. 
        # For example:
        # short: 1,3,4
        # long : 2,5,9,10
        # mergerd: 1,(2),3,4,(5),(9),(10)
        # here we have: median happened at index = 3 <== (3+5)/2 = 4th number, as the median number, thus
        # including the median number, the left has a total of 4 numbers, three are from short, only one is from long.
        # to find out the "three" and "one", which are the numbers contributed from both long, and short, we could easily identify the median number of the merged array.
        # so we do the following to ensure that we are operating on the short and long lists by redefining them:
        
        if a > b:
            short = b
            short_v = nums2
            long = a
            long_v = nums1
            imax = b
        else:
            short = a
            short_v = nums1
            long = b
            long_v = nums2
            imax = a
            
        imin = 0
        
        if long == 0:
            raise ValueError
          
        median_index = (length+1) // 2 
        
        #let us define ptrs imin, imax, 
        # recall the example, short, long
        # consider the imin, and imax are searched range for i ptr, on the short array:
        # thus, imin starts at 0, imax starts from the end of short array.
        # thus, imin = 0, imax = len(short) at the begining.
        # performing the binary search on the short array, we could narrow down the imin, imax range, adn finally locate the i index at short, so that we could know j index at long, both numbers including ith, jth in short and long, contributed towards the left part of the merged array.
        
        #binary search:
        while imin <= imax:
            # binary search guess i happen at the middle
            i = (imin+imax) // 2
            # derive j, according to i, known that how many numbers should exist in left
            j = median_index - i
            # validate the guess and iterate
            # if the i does not exceed the short, and the long last contributed is larger than the next remaining of the short, meaning the long contributed last one should not count, but should be the shor16. 
 
            elif i> 0 and short_v[i-1] > long_v[j]:
                imax = i-1
                
            #eventually, we should have the perfect i, that indicated short contributed i numbers, long contributed j numbers, the last contirbuted short number is smaller than the remining of the long. and long's last contributed number is also smaller than the short remaining next number.
            
            else:
            # we need consider several cases when i, or j could be zero, otherwise, the max left will be the maximum between each long and short contributed last number
                if i == 0: max_left = long_v[j-1]
                elif j == 0: max_left = short_v[i-1]
                else: max_left = max(long_v[j-1],short_v[i-1])
                
                # if the merged size is odd, the max_left is the single number, which should be the last number of left part
                if (length) % 2 == 1:
                    return max_left
                
                # we also need to consider when all short or all long contributed, as well as when the merged size is even:
                if i == short: min_right = long_v[j]
                elif j == long: min_right = short_v[i]
                #then the min_right is the minimum between the long remaining next and short remaining next
                else: min_right = min(long_v[j], short_v[i])
                #return the median calculation from left and right. 
                return(max_left+min_right) /2.0

双指针算法，链表，经典练习题

LeetCode-876 Middle of the Linked List

链表中点问题。

快慢指针找链表中点，经典idea。此题条件：If there are two middle nodes, return the second middle node.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head):
        # Write your code here
        if head is None:
            return None
        slow = head
        fast = slow
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
 
        return slow

228 Middle of Linked List

快慢指针找链表中点，经典idea。此题条件：If there are two middle nodes, return the first middle node.

"""
Definition of ListNode
class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
 
class Solution:
    """
    @param head: the head of linked list.
    @return: a middle node of the linked list
    """
    def middleNode(self, head):
        # write your code here
        if head is None:
            return None
        slow, fast = head, head.next
        while fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next
        
        return slow

双指针算法, Two Sum 变形题

610 Two Sum - Difference equals to target

同向双指针解决此题

class Solution:
    """
    @param nums: an array of Integer
    @param target: an integer
    @return: [num1, num2] (num1 < num2)
    """
    def twoSum7(self, nums, target):
        if not nums:
            return [-1, -1]
            
        target = abs(target)
        j = 1
        for i in range(len(nums)):
            j = max(j, i + 1)
            while j < len(nums) and nums[j] - nums[i] < target:
                j += 1
            if j >= len(nums):
                break
            if nums[j] - nums[i] == target:
                return [nums[i], nums[j]]
                
        return [-1, -1]

607 Two Sum III - Data structure design

数据结构版本的Two Sum之双指针解法

class TwoSum:
 
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums = []
        
 
    def add(self, number):
        """
        Add the number to an internal data structure..
        """
        self.nums.append(number)
 
    def find(self, value):
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        """
        n = len(self.nums)
        if n == 0:
            return False
        
        self.nums.sort()
        
        start, end = 0, n - 1
        while start < end:
            if self.nums[start] + self.nums[end] > value:
                end -= 1
            elif self.nums[start] + self.nums[end] == value:
                return True
            else:
                start += 1
        
        return False
 
# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)

数据结构版本的Two Sum之Hash dict()解法

class TwoSum(object):
 
    def __init__(self):
        # initialize your data structure here
        self.count = {}
        
 
    # Add the number to an internal data structure.
    # @param number {int}
    # @return nothing
    def add(self, number):
        # Write your code here
        if number in self.count:
            self.count[number] += 1
        else:
            self.count[number] = 1
 
        
 
    # Find if there exists any pair of numbers which sum is equal to the value.
    # @param value {int}
    # @return true if can be found or false
    def find(self, value):
        # Write your code here
        for num in self.count:
            if value - num in self.count and \
                (value - num != num or self.count[num] > 1):
                return True
        return False

57 3Sum

这道题非常好，它结合了 2sum 这道题和 2sum II sorted array 的解。

双指针 + 三指针 + twoSUM （sorted array）的转换，以及经典的去重检测。经典题目！！！

class Solution:
    def threeSum(self, nums):
        n = len(nums)
        if not nums or n < 3:
            return []
        ### 先sort一遍。   
        nums.sort()
        res = []
        
        for i in range(n - 2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            ###
            target = -nums[i]
            start, end = i + 1, n - 1
            
            while start < end:
                if nums[start] + nums[end] < target:
                    start += 1
                elif nums[start] + nums[end] > target:
                    end -= 1
                else:
                    res.append([nums[i], nums[start], nums[end]])
                    ### avoid duplicate 
                    while start < end and nums[start] == nums[start + 1]:
                        start += 1
                    while start < end and nums[end] == nums[end - 1]:
                        end -= 1
                    start += 1
                    end -= 1
        return res

587 Two Sum - Unique pairs

相向双指针

解法1 双指针 + 利用tuples来大擂台的小技巧

class Solution:
    """
    @param nums: an array of integer
    @param target: An integer
    @return: An integer
    """
    def twoSum6(self, nums, target):
        # write your code here
        if not nums or len(nums) <= 2:
            return 0
        ### to use two pointers, sort first
        nums.sort()
        
        left, right = 0, len(nums) - 1
        count = 0
        
        ###利用tuple来打擂台！小技巧！！超级实用还省时间空间。
        last_pair = (None, None)
        
        while left < right:
            if nums[left] + nums[right] == target:
                if (nums[left] , nums[right]) != last_pair:
                    ### 更新count和last_pair
                    count += 1
                    last_pair = (nums[left] , nums[right])
                left += 1
                right -= 1
            elif nums[left] + nums[right] > target:
                right -= 1
            else:
                left += 1
        
        return count

解法2 双指针 + 经典去重操作

class Solution:
    """
    @param nums: an array of integer
    @param target: An integer
    @return: An integer
    """
    def twoSum6(self, nums, target):
        # write your code here
 
        if not nums or len(nums) < 3:
            return 0
            
        nums.sort()
        
        left, right = 0, len(nums) - 1
        
        count = 0
        
        while left < right:
            if nums[left] + nums[right] == target:
                count += 1
                left += 1
                right -= 1
                ### 经典相向双指针去重操作：
                ### 注意下标，和谁比
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
 
            elif nums[left] + nums[right] > target:
                right -= 1
            else:
                left += 1
        
        return count

解法3 Hashmap + 去重复判断条件

class Solution:
    """
    @param nums: an array of integer
    @param target: An integer
    @return: An integer
    """
    def twoSum6(self, nums, target):
        # write your code here
        if not nums or len(nums) < 3:
            return 0
            
        counter = {}
        
        for num in nums:
            counter[num] = counter.get(num, 0) + 1
        
        res = 0
 
        for num, count in counter.items():
            diff = target - num
            if num <= target // 2 and diff in counter and (num != diff or count > 1):
                res += 1
        return res

LeetCode-611 Valid Triangle Number & 382 Triangle Count

这题属于3Sum 的引申版本。

此题的解的个数是Cn3，也就是说N^3。

但我们使用O(n^2)的时间复杂度就可以解，是因为我们优化的时候是按批计数的。res = res + right - left。

O(n^2) 优化解

class Solution:
    def triangleNumber(self, nums):
        if not nums or len(nums) < 3:
            return 
 
        nums.sort()
        ### Two Pinters:
        res = 0
        ### iterate all target
        for i in range(len(nums)):
            ### Apply two pointers, two sum type
            left, right = 0, i - 1
            while left < right :
                if nums[left] + nums[right] > nums[i]:
                    ### 如果right 可以， 那么right不变，left如果取这里一次性把left到right 所有数字也可以。
                    res = res + right - left
                    right -= 1
                else:  
                    left += 1
        return res

与此题相似的还有以下3题。

443 Two Sum - Greater than target

Triangle Count 基础。

解

class Solution:
    """
    @param nums: an array of integer
    @param target: An integer
    @return: an integer
    """
    def twoSum2(self, nums, target):
        # write your code here
        if not nums or len(nums) < 2:
            return 0
        nums.sort()
        res = 0
        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left] + nums[right] > target:
                res += right - left
                right -= 1
            else:
                left += 1
        
        return res

609 Two Sum - Less than or equal to target

Triangle Count 基础。

解

class Solution:
    """
    @param nums: an array of integer
    @param target: an integer
    @return: an integer
    """
    def twoSum5(self, A, K):
        # write your code here
        if not A:
            return 0
        
        A.sort()
        res = 0
        left, right = 0, len(A) - 1
        while left < right:
            if A[left] + A[right] > K:
                right -= 1
            else:
                res += right - left
                left += 1
        return res

LeetCode-1099 Two Sum Less Than K

Triangle Count 基础。

解

class Solution:
    def twoSumLessThanK(self, A, K):
        if not A:
            return -1
        
        A.sort()
        res = -1
        left, right = 0, len(A) - 1
        while left < right:
            if A[left] + A[right] >= K:
                right -= 1
            else:
                res = max(res, A[left] + A[right])
                left += 1
        return res

533 Two Sum - Closet to target

Two Sum 的引申。此题注意的是计算新diff的符号问题

class Solution:
    """
    @param nums: an integer array
    @param target: An integer
    @return: the difference between the sum and the target
    """
    def twoSumClosest(self, nums, target):
        # write your code here
        if not nums:
            return 
        
        nums.sort()
        
        left, right = 0, len(nums) - 1 
        diff = sys.maxsize
        while left < right :
            if nums[left] + nums[right] > target:
                ### 这里注意计算diff的符号问题
                diff = min(nums[left] + nums[right] - target, diff)
                right -= 1
            elif nums[left] + nums[right] < target:
                ### 这里注意计算diff的符号问题
                diff = min(target - nums[left] - nums[right], diff)
                left += 1
            else:
                return 0
        return diff

59 3Sum Closest

Three Sum 的引申，和Two Sum Closest 同理

### Two Pointers:
class Solution:
    def threeSumClosest(self, nums, target):
        if not nums or len(nums) < 3:
            return 
        
        nums.sort()
        
        res = None
        ### iterate the target, after sorting, reducing the searching range each time.
        for i in range(len(nums) - 2):
            left = i + 1
            right = len(nums) - 1
            while left < right:
                SUM = nums[i] + nums[left] + nums[right]
                if res == None:
                    res = SUM
                if abs(SUM - target) < abs(res - target):
                    #update res
                    res = SUM
                if SUM > target:
                    right -= 1
                elif SUM == target:
                    return SUM
                else:
                    left += 1
                    
        return res

58 4Sum

Three Sum 的引申，和Three Sum 同理, 去重操作，因为要返回unique解

 
### Find a + b + c + d = target:
 
class Solution:
    def fourSum(self, nums, target):
        if not nums or len(nums) < 4:
            return
        ### 先sort
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            ### 去重a
            if i > 0 and nums[i - 1] == nums[i]:
                continue
            for j in range(i + 1, n):
                ### 去重b
                ### 这里 j > i + 1 是十分必要的，因为要避免 nums[i] = nums[j] at j = i + 1 被跳过的情况。
                if j > i + 1 and nums[j - 1] == nums[j]:
                    continue
                ### Now convert the 4 sum to 2 Sum problem with the rest array.
                new_target = target - nums[i] - nums[j]
                self.twoSum(nums, i, j, n - 1, new_target, res)
        return res
    
    def twoSum(self, nums, i, j, end, new_target, res):
        left, right = j + 1, end
        while left < right:
            if nums[left] + nums[right] > new_target:
                right -= 1
            elif nums[left] + nums[right] == new_target:
                res.append([nums[i], nums[j], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left - 1] == nums[left]:
                    left += 1
                while left < right and nums[right + 1] == nums[right]:
                    right -= 1
            else:
                left += 1
        return

LeetCode-454 4SumII

a, b, c, d from 4 lists. find a + b + c + d = 0, how many pairs.

4Sum 的变形。

利用hashmap存任意 a+b 的和，然后枚举任意c+d的和，然后再用hashmap方法求two Sum。非常有意思的一道题目。

参考：https://leetcode.com/problems/4sum-ii/solution/

时间复杂度和空间复杂度均为 O(n^2) 将 a,b 组成的和及其组成方案个数统计在hash里，然后再去枚举 c,d 的组合，然后找 -(c+d) 在 hash 里的组合数。

Hashmap解法（经典）

class Solution:
    def fourSumCount(self, A, B, C, D):
        counter = {}
        for a in A:
            for b in B:
                counter[a + b] = counter.get(a + b, 0) + 1
        answer = 0
        for c in C:
            for d in D:
                answer += counter.get(-c - d, 0)
        return answer

Partition 类型练习题

31 Partition Array

Partition Array 经典双指针 QuickSelect O（n）解

class Solution:
    """
    @param nums: The integer array you should partition
    @param k: An integer
    @return: The index after partition
    """
    def partitionArray(self, nums, k):
        # write your code here
        if not nums:
            return 0
        left, right = 0, len(nums) - 1
       
        while left <= right:
            
            while left <= right and nums[right] >= k:
                right -= 1
            while left <= right and nums[left] < k:
                left += 1
            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
 
        return left

144 Interleaving Positive and Negative Numbers

想法：先确定正负数个数，再in-place partition分正负，再利用双指针一遍 in-place交换要求不花费额外空间。

Partition + 双指针

class Solution:
    """
    @param: A: An integer array.
    @return: nothing
    """
    def rerange(self, A):
 
        pos, neg = 0, 0
        for num in A:
            if num > 0:
                pos += 1
            else:
                neg += 1
                
        ### partition in-place
        self.partition(A, pos > neg)
        
        ### interleave in-place
        self.interleave(A, pos == neg)
            
    def partition(self, A, start_positive):
        ### use flag to arrange the partition
        flag = 1 if start_positive else -1
        left, right = 0, len(A) - 1
        while left <= right:
            while left <= right and A[left] * flag > 0:
                left += 1
            while left <= right and A[right] * flag < 0:
                right -= 1
            if left <= right:
                A[left], A[right] = A[right], A[left]
                left += 1
                right -= 1
    
    def interleave(self, A, has_same_length):
        left, right = 1, len(A) - 1
        ### according the length we need to determine the pointer start position
        
        ### EX:
        ### equal length:
        ### -----+++++
        ###  L      R
        ### -+---+++-+
        ###    L  R
        ### -+-+-+-+-+
        
        if has_same_length:
            right = len(A) - 2
            
        while left < right:
            A[left], A[right] = A[right], A[left]
            left, right = left + 2, right - 2

373 Partition Array by Odd and Even & LeetCode-Sort Array By Parity

Partition Array 经典双指针判断条件为奇偶数，此题为LeetCode版本题解

class Solution:
    def sortArrayByParity(self, A):
        
        left, right = 0, len(A) - 1
        while left <= right:
            while left <= right and A[left] % 2 == 0:
                left += 1
            while left <= right and A[right] % 2 != 0:
                right -= 1
            
            if left <= right:
                A[left], A[right] = A[right], A[left]
                left += 1
                right -= 1
        return A

49 Sort Letters by Case

Partition Array 经典双指针判断条件为letter的大小写

class Solution:
    """
    @param: chars: The letter array you should sort by Case
    @return: nothing
    """
    def sortLetters(self, chars):
        # write your code here
        # 定义左右指针并初始化
        left = 0
        right = len(chars) - 1
 
        # 两指针相向移动，交会则结束
        while left <= right:
            # 左指针向右移动，直到找到第一个大写字母
            while left <= right and chars[left] >= 'a' and chars[left] <= 'z':
                left += 1
 
            # 右指针向左移动，直到找到第一个小写字母
            while left <= right and chars[right] >= 'A' and chars[right] <= 'Z':
                right -= 1
 
            # 将左边的大写字母和右边的小写字母交换位置
            if left <= right:
                tmp = chars[left]
                chars[left] = chars[right]
                chars[right] = tmp
                left += 1
                right -= 1

148 Sort Colors

此题可以通过partition的方法一0， 1 分别作pivot，两次scan完成, Space O(1) 。或者是通过counting sort的方法，也是两次scan完成。都是O（n）解, Space O(n)。

普通解：两次扫描，双指针quicksort优化版

class Solution:
    def sortColors(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        left, right = 0, len(nums) - 1
        new_left = self.partition(nums, left, right, 0)
        self.partition(nums, new_left, right, 1)
                
    def partition(self, nums, left, right, pivot):
        while left <= right:
            while left <= right and nums[right] != pivot:
                right -= 1
            while left <= right and nums[left] == pivot:
                left += 1
            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        return left

最优解：基于双指针的三指针 One Pass （一次扫描 O(n)) 最优解

class Solution:
    def sortColors(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        # for all idx < p0 : nums[idx < p0] = 0
        # curr is an index of element under consideration
 
        ### p0 : ptr to zeros,
        ### p2 : ptr to twos
        ### curr : should be ptr on ones
 
        ### the move on p0 and p2 depends on curr's value
 
        p0 = curr = 0
        # for all idx > p2 : nums[idx > p2] = 2
        p2 = len(nums) - 1
 
        while curr <= p2:
            if nums[curr] == 0:
                nums[p0], nums[curr] = nums[curr], nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[curr], nums[p2] = nums[p2], nums[curr]
                p2 -= 1
            else:
                curr += 1

625 Partition Array II

同样类似于sort colors的题型，使用三指针来分成三份，并且对unsorted in place partition。经典题目。

三指针 One Pass 解

class Solution:
    """
    @param nums: an integer array
    @param low: An integer
    @param high: An integer
    @return: nothing
    """
    def partition2(self, nums, low, high):
        # write your code here
        """
        Do not return anything, modify nums in-place instead.
        """
        ### one pass three pointers
        # for all idx < plow : nums[idx < plow] < low
        # curr is an index of element under consideration
        plow = curr = 0
        # for all idx > phigh : nums[idx > phigh] > high
        phigh = len(nums) - 1
 
        while curr <= phigh:
            if nums[curr] < low:
                nums[plow], nums[curr] = nums[curr], nums[plow]
                plow += 1
                curr += 1
            elif nums[curr] > high:
                nums[curr], nums[phigh] = nums[phigh], nums[curr]
                phigh -= 1
            else:
                curr += 1

LeetCode-11 Container With Most Water

相向双指针经典解：（One Pass）

class Solution:
    def maxArea(self, nums):
        if not nums:
            return 0
        left, right = 0, len(nums) - 1
        area = 0
        while left < right:
            if nums[left] <= nums[right]:
                curr_area = (right - left) * nums[left]
                left += 1
            else:
                curr_area = (right - left) * nums[right]
                right -= 1
            if curr_area >= area:
                area = curr_area
        return area

143 Sort Colors II (Rainbow Sort)

经典排序，Rainbow Sort，复杂度为O(nlogk), 以k二分作为partition的判断标准。又有些类似merge sort。

（分治法），注意，merge sort和这题都只能些小于等于，不能用小于。因为会造成左侧没有elements。

实际操作是quicksort，但是对k的区间变化是mergesort，这题需要好好记住。

Rainbow Sort

class Solution:
    
    """
 
    @param colors: A list of integer
 
    @param k: An integer
 
    @return: nothing
 
    """
 
    def sortColors2(self, colors, k):
 
        self.sort(colors, 0, len(colors) - 1, 1, k)
 
        
 
    def sort(self, colors, start, end, colorFrom, colorTo):
 
        #若处理区间长度为小于等于1或颜色区间长度为1，则不需要再进行处理
 
        if start >= end or colorFrom == colorTo:
 
            return
 
        #设置左右指针以及中间的颜色， 利用中点。  
 
        colorMid = colorFrom + (colorTo - colorFrom) // 2
 
        left, right = start, end
 
        while left <= right:
 
            #找到左侧大于中间颜色的位置, 注意这里colors必须是小于等于。避免左侧没有数。
 
            while left <= right and colors[left] <= colorMid:
 
                left += 1
 
            #找到右侧小于等于中间颜色的位置
 
            while left <= right and colors[right] > colorMid:
 
                right -= 1
 
            #交换左右指针指向的颜色
 
            if left <= right:
 
                colors[left], colors[right] = colors[right], colors[left]
 
        #继续递归处理左右两半序列
 
        self.sort(colors, start, right, colorFrom, colorMid)
 
        self.sort(colors, left, end, colorMid + 1, colorTo)

经典同向双指针，优化，练习题

559 Move Zeros

普通解 + 最优解 + Explain

### 无法保证minimize的普通解， 机遇swap。
class Solution:
    """
    @param nums: an integer array
    @return: nothing
    """
    def moveZeroes(self, nums):
        left, right = 0, 0
        while right < len(nums):
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1
            
 
### 保证minimize的最优解， 不着急swap，先赋值，最后直接改。
class Solution:
    def moveZeroes(self, nums):
        """
        Do not return anything, modify nums in-place instead.
        """
        ### minimize the write operations:
        ### EX:
        ### 1 0 2 3 0
        ### L
        ### R
        ### 1 0 2 3 0
        ###   L
        ###   R(nums[R] == 0, skip)
        ### 1 0 2 3 0
        ###   L
        ###     R(nums[R] != 0, change  L, L += 1)
        ### 1 2 2 3 0
        ###     L
        ###       R(nums[R] != 0, change  L, L += 1)
        ### 1 2 3 3 0
        ###       L
        ###         R(nums[R] == 0, skip, end of loop)
        ### 1 2 3 3 0
        ###       L (L is not zero, change to 0, L += 1)
        ### 1 2 3 0 0
        ###         L (end)
        # write your code here
        left, right = 0, 0
        while right < len(nums):
            if nums[right] != 0:
                if left != right:
                    nums[left] = nums[right]
                left += 1
            right += 1
            
        while left < len(nums):
            if nums[left] != 0:
                nums[left] = 0
            left += 1

LeetCode-26 Remove Duplicates from Sorted Array

同向双指针，经典题目！！！

class Solution:
    def removeDuplicates(self, nums):
        if not nums:
            return 0
        j = 1
        for i in range(len(nums)):
            while j < len(nums) and nums[j] == nums[i]:
                j += 1
            if j >= len(nums):
                break
            nums[i + 1] = nums[j]
        return i + 1

521 Remove Duplicate Numbers in Array

普通解，Hash， extra space， O（n）

class Solution:
    """
    @param nums: an array of integers
    @return: the number of unique integers
    """
    def deduplication(self, nums):
        # Write your code here
        if not nums:
            return 0
            
        unique = list(set(nums))
        nums[:len(unique)] = unique
        
        return len(unique)

普通解（同向双指针）， O（nlogn）

class Solution:
    """
    @param nums: an array of integers
    @return: the number of unique integers
    """
    def deduplication(self, nums):
        # Write your code here
        n = len(nums)
        if n == 0:
            return 0
            
        nums.sort()
        result = 1
        for i in range(1, n):
            if nums[i - 1] != nums[i]:
                nums[result] = nums[i]
                result += 1
                
        return result

经典同向双指针模板解法 O（nlogn）

class Solution:
    """
    @param nums: an array of integers
    @return: the number of unique integers
    """
    def deduplication(self, nums):
        # Write your code here
        if not nums:
            return 0
        nums.sort()
        j = 1
        for i in range(len(nums)):
            while j < len(nums) and nums[j] == nums[i]:
                j += 1
            if j >= len(nums):
                break
            nums[i + 1] = nums[j]
        return i + 1

LeetCode 340 Longest Substring with At Most K Distinct Characters

一次遍历即可遍历的同时记录: 每个字符出现的次数, 当前子串中不同字符的个数其中定义一个变量记录左边界, 当前子串即左边界到遍历位置对应的子串如果不同字符的个数超过k, 则向右调整左边界即可, 遍历同时维护最长子串长度即可

经典同向双指针 O(N) Sliding Window + ordererd Dict 解法非常经典！！！

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s, k):
        if not s:
            return 0
            
        counter = {}
        left = 0
        longest = 0
        
        for right in range(len(s)):
            counter[s[right]] = counter.get(s[right], 0) + 1
            while left <= right and len(counter) > k:
                counter[s[left]] -= 1
                if counter[s[left]] == 0:
                    del counter[s[left]]
                left += 1
            
            longest = max(longest, right - left + 1)
        return longest

1375 Substring With At Least K Distinct Characters

经典同向双指针 O(N) Sliding Window + ordererd Dict 解法非常经典！！！

class Solution:
    """
    @param s: a string
    @param k: an integer
    @return: the number of substrings there are that contain at least k distinct characters
    """
    def kDistinctCharacters(self, s, k):
        # Write your code here
        left = 0
        counter = {}
        answer = 0
        for right in range(len(s)):
            counter[s[right]] = counter.get(s[right], 0) + 1
            while left <= right and len(counter) >= k:
                counter[s[left]] -= 1
                if counter[s[left]] == 0:
                    del counter[s[left]]
                left += 1
                    
            if len(counter) == k - 1 and left > 0 and s[left - 1] not in counter:
                answer += left
                
        
        return answer

1343 Sum of Two Strings

class Solution:
    """
    @param A: a string
    @param B: a string
    @return: return the sum of two strings
    """
    def SumofTwoStrings(self, A, B):
        # write your code here
        if not A:
            if not B:
                return '0'
            else:
                return B
        if not B:
            return A
        
        
        len_A, len_B = len(A), len(B)
        res = ''
        while len_A > 0 and len_B > 0:
            res = str(int(A[len_A - 1]) + int(B[len_B - 1])) + res
            len_A -= 1
            len_B -= 1
        
        if len_A > 0:
            res = A[0 : len_A] + res
        if len_B > 0:
            res = B[0 : len_B] + res
        
        return res

Comments