双指针题集锦

LeetCode 977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

https://leetcode-cn.com/problems/squares-of-a-sorted-array/

思路

既然已知给的数组是排好序的，棘手的地方就是负数，因此考虑用两个指针，分别从最大和最小两端出发，比较两端大小，将较大的结果放入结果数组的最后，然后指针前进。这个方法比起另一种先找到正负边界再进行归并排序的方法更加优雅，而且不需要考虑边界的问题，实现更为简单。还有比较基础的，先算好所有平方的值再进行排序的方法，比较拉，不多赘述。

这题的解题模板跟二分搜索的模板类似，只需要多做一个变通，加入一个pos指示当前结果数组的位置。

时间复杂度为O(n)，空间复杂度为O(1)。

题解

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1, pos = nums.length - 1;
        int[] res = new int[nums.length];
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                res[pos] = nums[left] * nums[left];
                left++;
            } else {
                res[pos] = nums[right] * nums[right];
                right--;
            }
            pos--;
        }
        return res;
    }
}

LeetCode 189. 轮转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

https://leetcode-cn.com/problems/rotate-array/

思路

当我们将数组的元素向右移动 k 次后，尾部 k mod n 个元素会移动至数组头部，其余元素向后移动 k mod n 个位置。因此完成轮转只需要三步：

1. 将整个数组翻转，此时尾部k mod n个元素在前面；
2. 翻转[0, k mod n - 1]，使得原来尾部的元素按正常顺序排列；
3. 翻转[k mod n, n-1]，使得原来头部的元素按正常顺序排列。

题解

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++; end--;
        }
    }
}

LeetCode 283. 移动零

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

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

https://leetcode-cn.com/problems/move-zeroes/

思路

容易想到用快慢指针，快的指针一直往前走，遇到非0时停下，与慢指针交换，然后慢指针往前走一步，快指针继续往前走，直到快指针走完循环中止。

一开始想法有点偏差，想把慢指针初始化为0，快指针初始化为1，用当慢指针遇到零，快指针往前走到非零，与慢指针交换，然后慢指针往前走一步，直到快指针走完循环中止。比这个正解多套了一层，且没法很好地管理边界情况。

题解

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != 0) {
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
            fast++;
        }
    }
}

LeetCode 167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

思路

指针从两遍开始走，如果左右指针相加大于目标值，说明右边太大了，这时候右边指针-1；如果小于目标值，说明左边太小了，左边指针+1；两个指针相加等于目标值即为答案。

题解

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int slow = 0, fast = numbers.length - 1;
        while (slow < fast) {
            int cur = numbers[slow] + numbers[fast];
            if (cur > target) {
                fast--;
            } else if (cur < target) {
                slow++;
            } else if (cur == target) {
                return new int[] {slow + 1, fast + 1};
            }
        }
        return new int[] {-1, -1};
    }
}