今天继续学习python。数组（list）在python里面，好灵活啊。各种列表方法，切片，迭代器看得我一愣一愣的。以前c++做题都是老老实实for，现在一句话就写完了，只是不知道这些方法的复杂度是多少……要学的东西越来越多了。

    遍历操作时间复杂度O(n)，手册里面的题解，直接在原地开了一个最高位补零，按位加，再用切片去掉最高位的零。那么切片的时间复杂度是多少呢？按道理来说insert操作的时间复杂度也是O(n)吗，先append再逆序可能会更优一些。

    1. class Solution:
    2.     def plusOne(self, digits: List[int]) -> List[int]:
    3.         n = 0
    4.         for num in digits:
    5.             n = n * 10 + num
    6.         n += 1
    7.         l = []
    8.         while n:
    9.             l.append(n%10)
    10.             n //= 10
    11.         return l[::-1]

    前缀和思想。只要知道总和就能知道后缀和(total_sum - pre_sum)。时间复杂度O(n)。

    1. class Solution:
    2.     def pivotIndex(self, nums: List[int]) -> int:
    3.         n = len(nums)
    4.         s = sum(nums)
    5.         s_pre = 0
    6.         for i in range(n):
    7.             if  s_pre  == s - s_pre - nums[i]:
    8.                 return i
    9.             s_pre += nums[i]  
    10.         return -1

    我的想法是先把nums拼接起来，拼接处正好就是旋转之后的样子，按照k把前后裁剪掉就好了。注意k可能会超过数组长度，从而重复旋转多次，对k取模即可保证只旋转一次。但是这种方法把原数组延长复制了一遍空间复杂度O(n)
    题解的方法是全列表翻转，按k分两段，分别对左右再翻转，这样空间复杂度可以优化到O(1)，时间复杂度都是O(n)

    1. class Solution:
    2.     def rotate(self, nums: List[int], k: int) -> None:
    3.         """
    4.         Do not return anything, modify nums in-place instead.
    5.         """
    6.         n = len(nums)
    7.         k %= n
    8.         nums.extend(nums)
    9.         nums[:n-k]=[]
    10.         nums[n:]=[]