双指针应用

Leetcode 283 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

提示:

1 < = n u m s . l e n g t h < = 1 0 4 − 2 3 1 < = n u m s [ i ] < = 2 3 1 − 1 1 <= nums.length <= 10^4 \ -2^31 <= nums[i] <= 2^31 - 1 1<=nums.length<=104−231<=nums[i]<=231−1

定义两个指针，指针 i 指向当前正在遍历的元素下标，指针 j 指向 非零 元素的个数

i 和 j 初始化为 0，遍历整个数组，如果遇到非零元素，则直接赋值给 j 指针指向地址，然后 j++

class Solution {
public:
	void moveZeros(vector& nums) {
        int len = nums.size();
        int j = 0; // j 指针指向非零元素的个数
        // 遍历数组
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i]; // 将非零元素放到排头，将零元素移到末尾
            }
        }
        for (int i = j; i < len; i++) {
            nums[i] = 0; // 数组剩下的元素就都是0了
        }
    }
}

448 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

输入：nums = [1,1]
输出：[2]

提示：

n = = n u m s . l e n g t h 1 < = n < = 1 0 5 1 < = n u m s [ i ] < = n n == nums.length \ 1 <= n <= 10^5 \ 1 <= nums[i] <= n n==nums.length1<=n<=1051<=nums[i]<=n

本题可以在原有数组中进行操作

改变数组中出现过的元素，使没有出现的元素不被修改，这样，就很容易找出不在数组中的元素了

修改方法可以修改为负数，这样存在数组的数就都是负数，没有出现的数就是正数

或者进行 + n ，这样没有出现在数组中的数就一定比 n 小，因为数组中的元素在[1, n] 之间

这样没有出现在数组中的数字就求出来了，所有 ≤ n leq n ≤n 的数字都是没有出现的数字，其对应的小标就是本题的解，但是下标范围是 [0, n - 1] ，所以结果要 + 1

class Solution {
    public List findDisappearedNumbers(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            // 找到对应下标
            int k = (nums[i] - 1) % length;
            // 修改数组中出现的数字
            nums[k] += length;
        }
        List list = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            // 没有被修改的数字存入list中
            if (nums[i] <= length) {
                list.add(i + 1);
            }
        }
        return list;
    }
}