[数据结构与算法]leetcode: 2 pointers

算法分析

该类题型是很好理解，应该先刷，双指针一般会遇到两种类型，一类是数组双指针在两端，一类是链表指针在两端。如leetcode 11, 15，16，18等等。使用双指针可以把时间从O(n^2)提高到O(n), 一般能减小一个n次方。觉得也没有必要完全按照标签来做，因为如果能用一种其他的方法解题也可以不考虑双指针，目的是解题，方法用自己最擅长的就可以。没有必要为了某一个解题方法重复做太多的题。关键是知道这样的方法。

11. Container With Most Water

1 lo: left pointer, hi: right pointer, at both side
2 this may have the largest value, then i to right, j to left
3 until lo >= hi, stop loops and return result

class Solution:
    def maxArea(self, height: List[int]) -> int:
        lo, hi = 0, len(height) - 1
        res = 0
        while lo < hi:
            res = max(res, min(height[lo], height[hi]) * (hi - lo))
            if height[lo] < height[hi]:
                lo += 1
            else:
                hi -= 1
        return res        

15. 3Sum

1 prepare a set：为了避免重复
2 sort the array：为了利用双指针
3 for each i loop, use 2 pointers to reduce time in sorted array
4 use set to avoid repeating
5 if i > 0 and nums[i] == nums[i-1]:为了加快速度

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = set()
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue # if already use i, no need to use any more
            low, high = i + 1, len(nums) - 1
            while low < high:
                three = nums[i] + nums[low] + nums[high]
                if three == 0:
                    res.add((nums[i], nums[low], nums[high]))
                    low += 1
                    high -= 1
                elif three < 0:
                    low += 1
                else:
                    high -= 1
        return res

16. 3Sum Closest

1 prepare a res = infinity
2 sort the array
3 for each i in loop, use 2 pointers to find the closest
4 if equals to target, return target
5 else return closest
6 if low >= high, output res
补充一句话加快速度

if i > 0 and nums[i] == nums[i-1]:
                continue

因为已经遍历过的元素没有必要再次遍历，再次遍历是的结果一定是他的子集

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        res = float('inf')
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            lo, hi = i + 1, len(nums) - 1
            while lo < hi:
                three = nums[i] + nums[lo] + nums[hi]
                if three == target:
                    return target
                if abs(three - target) < abs(res - target):
                    res = three
                if three < target:
                    lo += 1
                else:
                    hi -= 1
        return res

18. 4Sum

加上一句:if i > 0 and nums[i] == nums[i-1]: continue, 加快速度。

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        num_set = set()
        nums.sort()
        for i in range(len(nums) - 1):
            if i > 0 and nums[i] == nums[i-1]: continue
            for j in range(i + 1, len(nums)):
                lo, hi = j + 1, len(nums) - 1
                while lo < hi:
                    four = nums[i] + nums[j] + nums[lo] + nums[hi]
                    if four == target:
                        num_set.add((nums[i], nums[j], nums[lo], nums[hi]))
                        lo += 1
                        hi -= 1
                    elif four < target:
                        lo += 1
                    else:
                        hi -= 1
        return num_set

26. Remove Duplicates from Sorted Array

这是双指针的另一种写法， idx是一个慢指针， i是一个快指针。因为是排好序的数组，只要快指针遇到不一样的数字，那么把这个数字放到慢指针的位置上即可。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        idx = 1
        for i in range(1, len(nums)):
            if nums[i-1] != nums[i]:
                nums[idx] = nums[i]
                idx += 1
        return idx

151. Reverse Words in a String

既然用python, 必然会用到各种的库，没有必要想加入用其他的程序语言怎么写，split, 怎么写join, 我们需要做的就是如何用，毕竟我们不是C++算法高手。本题用到双指针就可以了，当然可以直接用reverse. 但是接下来的问题是in place，所以解法1， 2不行。方法3才是in place，这样就得用到C++的方法了。

方法1：

class Solution:
    def reverseWords(self, s: str) -> str:
        lst = s.split()
        lo, hi = 0, len(lst) - 1
        while lo < hi:
            lst[lo], lst[hi] = lst[hi], lst[lo]
            lo += 1
            hi -= 1
        return " ".join(lst)

方法2：

class Solution:
    def reverseWords(self, s: str) -> str:
        lst = s.split()
        lst.reverse()
        return " ".join(lst)

方法3：全部双指针

class Solution:
    def reverseWords(self, s: str) -> str:
        res, i, n = '', 0, len(s)
        
        while i < n: # if i out of loop, stop
            while i < n and s[i] == ' ':
                i += 1
            if i >= n:
                break
            j = i + 1
            while j < n and s[j] != ' ':
                j += 1
            sub = s[i: j]
            if len(res) == 0:
                res = sub # the first word: hello
            else:
                res = sub + " " + res # reverse
            i = j + 1 # next word: world
        return res