力扣刷题-数组-双指针法总结-移除元素

注意

注意一点，数组中的元素是不能删除的。要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。（所以是移动元素）

双指针法原理

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针：
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置

题目

27.移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
解题思路：
fast指针用来遍历数组中的原有元素，然后通过题目中的条件来判断，将需要移动到前面的元素通过slow指针移动（slow从0开始），相当于一个新的数组了。

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        # 双向指针法 巧妙之处
        fast, slow = 0, 0
        while fast < len(nums):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow # 注意不能是len(nums)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。（注意看清条件 再仔细分析 会更简单）
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

这题有两个巧妙之处：
fast指针的范围是[0, len(nums)-1-1] 因为下面判断条件是fast+1
slow += 1这个位置放的比较巧妙 因为第一个元素(slow=0)肯定是不会有之前重复的元素。

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0 # 不加这个也能够通过 但加了增强代码的健壮性
        slow= 0, 0
        for fast in range(len(nums)-1): # 因为后面是 fast+1
            if nums[fast] != nums[fast+1]:
                slow += 1 # 放在这个位置很妙 因为第一个肯定是
                nums[slow] = nums[fast+1]
        return slow + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14

283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
解题思路：题目意思是把所有移动到数组的末尾——>转换一下，就是把不是0的元素移到前面去，然后根据slow现在的大小来用0填充后面的位置

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # 题目意思是把所有移动到数组的末尾——>转换一下，就是把不是0的元素移到前面去
        slow, fast = 0, 0
        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow] = nums[fast] # 把非零元素移到前面
                slow += 1 
        nums[slow:] = [0] * (len(nums)-slow) # 把之后的元素填为0
        return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14

977. 有序数组的平方

这种也是双指针做法，不一定只有快慢才是双指针。
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result = [0] * len(nums) # 定义一个存储结果的数组 全部初始化为0
        i, j, k = 0, len(nums)-1, len(nums) - 1 # 这种也是类似双指针 不一定是快慢
        while i <= j: # =还是不=可以慢一点确定 先把大概逻辑确定 再去定细节
            if nums[i]**2 > nums[j]**2:
                result[k] = nums[i]**2
                i += 1
            else:
                result[k] = nums[j]**2
                j -= 1
            k -= 1
        return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

参考：https://programmercarl.com/