Two Points

26. 删除排序数组中的重复项

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

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

88. 合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/
我自己的解法， 代码有点冗长，但这道题逻辑很简单，是双指针入门题

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if n == 0:
            return nums1
        if m == 0:
            nums1[:]=nums2[:]
            return nums1
        if n == 0 and m == 0:
            return [] 
        i = m-1
        j = n-1
        point = -1
        while i>=0 and j>=0:
            if nums1[i] > nums2[j]:
                nums1[point] = nums1[i]
                i-=1
            else:
                nums1[point] = nums2[j]
                j-=1
            point-=1
# 无需判断i>=0,因为如果i>=0，说明所有nums2的元素都已经按顺序放进了nums1，而nums1原本就是有序的
        while j>=0:
            nums1[point] = nums2[j]
            j-=1
            point-=1
        return nums1

167. 两数之和 II - 输入有序数组

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
two points最简单的入门题

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        start = 0
        end =len(numbers)-1
        while start < end:
            if numbers[start] + numbers[end] == target:
                return [start+1,end+1]
            elif numbers[start] + numbers[end] > target:
                end-=1
            else:
                start+=1

283. 移动零

https://leetcode-cn.com/problems/move-zeroes/
一个point挨个遍历数组，一个point表示要把不为零的数往前挪的位置

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) < 2:
            return nums
        point = 0
        for i in range(len(nums)):
            if nums[i]!=0:
                nums[i], nums[point] = nums[point], nums[i]
                point+=1
        return nums

633. 平方数之和

https://leetcode-cn.com/problems/sum-of-square-numbers/
数学上是费曼大定理，算法上用two points就可以很高效的完成

from math import sqrt
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        start = 0
        end = int(sqrt(c))
        while start <= end:
            if start*start + end*end > c:
                end-=1
            elif start*start + end*end < c:
                start+=1
            else:
                return True
        return False

665. 非递减数列

https://leetcode-cn.com/problems/non-decreasing-array/
这道题可以用two points来判断，主要考虑的点是：

1. 是否有波谷
2. 不能有2个及以上波谷
3. 如果波谷发生在0 or len-1 处，没问题

4. 如果波谷发生的中间， 需要考虑波谷两元素及其一前一后一共四个元素的关系

   class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        if len(nums)<3:
            return True
        length = len(nums)
        left, right = 0, length-1
        while left<length-1 and nums[left]<=nums[left+1]:
            left+=1
        if left==length-1:
            return True
        while right>0 and nums[right]>=nums[right-1]:
            right-=1
        if right-left > 1:
            return False
        if left==0 or right==length-1:
            return True
        if nums[right+1]>=nums[left] or nums[left-1]<=nums[right]:
            return True
        else:
            return False

   74. 搜索二维矩阵

   https://leetcode-cn.com/problems/search-a-2d-matrix/
   这道题的关键就是从左下角开始遍历，根据target的大小决定是i-=1 or j+=1

   75. 颜色分类

   https://leetcode-cn.com/problems/sort-colors/