同向双指针

两个指针同向运动,用两个变量，一个变量记录当写指针的位置(fast index), 一个变量记录隔板位置(slow index).

• 性质1. slow左边是处理好的元素，当先指针fast右边是未处理的元素，两个指针之间的区域是无用的元素/每次只要分析当前元素性质是否要加入或者移动slow就可以！
• 性质2. 用快慢指针，同向而行，处理完毕之后，return的结果中，每个integer/char的相对位置不变！

1 Element Removal 删除元素

• 删除或者保留具有某些性质的元素

27. Remove Element

class Solution(object):
    def removeElement(self, nums, val):
        if not nums: return 0
        slow = 0
        for i in xrange(len(nums)):
            if nums[i] != val:
                nums[slow] = nums[i]
                slow += 1
        return slow

26. Remove Duplicates from Sorted Array

• 双指针，一个fast指针作为遍历指针，一个slow作为“有效值”指针
  • fast: all elements to the left hand side of slow (excluding slow) are the final results to return
  • slow: current index

class Solution(object):
    def removeDuplicates(self, nums):
        if not nums: return 0
        slow = 1 # slow为下一个“有效值”该放的位置
        for i in xrange(1, len(nums)):
            # 和前一个元素不相等，所以为“有效值”
            if nums[i] != nums[i-1]: # nums[i] != nums[slow-1] 也可以！
                nums[slow] = nums[i]
                slow += 1
        return slow

• Follow up

  • 最多保留一个相同元素 -> 保留两个? LeetCode80
  • 最多保留k个相同元素？
  • 一个都不保留，删除所有重复元素!!!

• slow : all elements to the left hand side of slow (excluding slow) are the final results to return.

• fast1: current index.
• fast2: 探路指针指向重复的最后一个
  • 根据fast1和fast2的距离判断重复

80. Remove Duplicates from Sorted Array II

• slow : all elements to the left hand side of slow (excluding slow) are the final results to return.
• fast : current index

class Solution(object):
    def removeDuplicates(self, nums):
        if len(nums) <= 2:
            return len(nums)

        slow = 2
        for i in xrange(2, len(nums)):
            # Key Point:遍历的当前位置和slow-2的位置比
            if nums[i] != nums[slow-2]:
                nums[slow] = nums[i]
                slow += 1
        return slow

283. Move Zeroes

• move all 0's to the end of it while maintaining the relative order of the non-zero elements.
• 由于要保证相对顺序不变，所以只能用同向双指针！
  • slow:all elements to the left hand side of slow (excluding slow) must be non zero.
  • fast: current index
  • [slow, fast]: unexplored subarray

class Solution(object):
    def moveZeroes(self, nums):
        non = 0
        for i in xrange(len(nums)):
            if nums[i] != 0:
                nums[non], nums[i] = nums[i], nums[non]
                non += 1

    def moveZeroes1(self, nums):
        slow = 0
        for i in xrange(len(nums)):
            if nums[i] != 0:
                nums[slow] = nums[i]
                slow += 1
        while slow <= len(nums)-1:
            nums[slow] = 0
            slow += 1

• What if we do not need to maintain the relative order of the elsements ?
  • 相向双指针

class Solution(object):
    def moveZeroes(self, nums):
        left = 0
        right = len(nums) - 1
        while left <= right:
            if nums[left] != 0:
                left += 1
            elif nums[right] == 0:
                right -= 1
            else:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        return left