283. 移动零

• 思路
  • example
  • 要求：in-place
  • 双指针，->->
    • 把非零元素移到前面，最后补0
• 复杂度. 时间：O(n), 空间: O(1)

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

• 尽量减少完成的操作次数
  • 交换，避免后面补0

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        left, right = 0, 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

189. 轮转数组

• 思路
  • example
  • 三种方法
  • 额外空间：先赋值nums[n-k:n] 到新数组res[0:k], 再赋值nums[0:n-k] 到新数组res[k:n-1]
  • in-place, 分两部分局部反转，再整体反转
    • 双指针
  • 注意：k可能大于n

k %= n

• 复杂度. 时间：O(n), 空间: O(1)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(nums, left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        n = len(nums)
        k %= n
        reverse(nums, 0, n-k-1)
        reverse(nums, n-k, n-1)
        reverse(nums, 0, n-1)

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(nums, left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left] 
                left += 1
                right -= 1
        n = len(nums) 
        k %= n 
        reverse(nums, 0, n-1) 
        reverse(nums, 0, k-1) 
        reverse(nums, k, n-1)

724. 寻找数组的中心下标

• 思路
  • example

current == total - nums[i] - current

• 复杂度. 时间：O(n), 空间: O(1)

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        n = len(nums)
        total = sum(nums)
        current = 0
        for i in range(n):
            if current == total - nums[i] - current:
                return i  
            current += nums[i]
        return -1

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        n = len(nums) 
        left = [0 for _ in range(n)] 
        right = [0 for _ in range(n)] 
        for i in range(1, n):
            left[i] = left[i-1] + nums[i-1] 
        for i in range(n-2, -1, -1):
            right[i] = right[i+1] + nums[i+1] 
        for i in range(n):
            if left[i] == right[i]:
                return i 
        return -1