1. tow sum(id=1)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result_dict = {}
        for i,n in enumerate(nums):
            if n in result_dict:
                return [result_dict[n],i]
            else:
                result_dict[target-n] = i 

2. Two Sum II - Input array is sorted(id=167)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        '''
        双指针
        '''
        l = 0
        r = len(numbers)-1
        while l<r:
            s = numbers[l]+numbers[r]
            if s==target:
                return [l+1,r+1]
            elif s<target:
                l +=1
            else:
                r -= 1

3. Two Sum IV - Input is a BST(id=653)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        if not root:
            return False
        return self._findTarget(root, k, set())
    

            
    def _findTarget(self, p: TreeNode, k: int, s :set):
        if not p:
            return False
        
        if p.val in s:
            return True
        else:
            s.add(k-p.val)
            return self._findTarget(p.left,k,s) or self._findTarget(p.right,k,s)
                

4. Remove Duplicates from Sorted Array(id=26)

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        tmp_set = set()
        num_len = len(nums)
        p = 0
        for i in nums:
            if i not in tmp_set:
                nums[p]=i
                p += 1
                tmp_set.add(i)
        return len(nums[:p])

5.Remove Element(id=27)

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        p = 0
        for i in nums:
            if i != val:
                nums[p] = i
                p += 1
        return len(nums[:p])

6.Search Insert Position(id=35)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i,n in enumerate(nums):
            if target<=n:
                return i
        return i+1

7. Maximum Subarray(id=53)

• 1.这方法完全想不到

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

8. Plus One(id=66)

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        length = len(digits)
        in_flag,digits[length-1] = divmod(digits[length-1]+1,10) 
        for i in range(length-2,-1,-1):
            in_flag,digits[i] =  divmod(in_flag+digits[i],10)
        if in_flag>0:
            digits.insert(0,in_flag)
        return digits

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        num = 0
        len_d = len(digits)
        for i,e in enumerate(digits):
            num += (10**(len_d-1-i) ) *e
        return [int(i) for i in str(num+1)]