【算法】双指针思想

一、Leetcode27.移除元素

1.题目描述

给你一个数组 nums和一个值 val，你需要 [原地] 移除所有数值等于 val的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 [原地 ]修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

2.暴力破解

public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < nums.length; j++) {
                    nums[j - 1] = nums[j];
                }
                size--;
                i--;
            }
        }
        return size;
    }

• size–: 当遇到了数组中和目标相等的元素，说明是要移除的，所以size–
• i–: 因为在遇到了需要移除的元素之后，是用后面的元素覆盖了前面的元素，所以当进入了if判断之后，说明后面一个待比较的新的元素已经移动到前一位去了，所以i–，才可以再比较到这个移动到了前面的新的元素。

3.双指针

  public static int removeElementDoublePoint(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }

定义一个快指针fast，用来正常的遍历元素；
定义一个慢指针slow，用来指向新的数组的元素（删除了目标元素后的）
没有遇到目标元素时所指向的元素（符合的元素），都存入新数组（slow指向）

二、Leetcode977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 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]

1.暴力破解

遍历数组的每一个元素，算出平方。再对结果进行排序

    public static int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        return insertSort(nums);
    }

    /**
     * 选择排序
     *
     * @param nums
     * @return
     */
    private static int[] selectSort(int[] nums) {
        for (int j = 0; j < nums.length; j++) {
            int minValueIndex = j;
            for (int k = j + 1; k < nums.length; k++) {
                // 找出索引最小的
                minValueIndex = nums[k] < nums[minValueIndex] ? k : minValueIndex;
            }
            //把找到的下标和第j个元素交换 nums[j] nums[minValueIndex]
            int temp = nums[j];
            nums[j] = nums[minValueIndex];
            nums[minValueIndex] = temp;
        }
        return nums;
    }

    /**
     * 插入排序
     *
     * @param nums
     * @return
     */
    private static int[] insertSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
        return nums;
    }

2.双指针

头指针和尾指针，头指针从下标0开始，尾指针从最后一个元素（下标nums.length-1）开始，头指针前进，尾指针后退，直到相遇就是遍历完了；遍历的过程中，每次都取出更大的那个数，存入一个新的数组中，从最后一个下标往前存，因为是非递减的。

    public static int[] sortedSquares(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        int[] sortedSquareNums = new int[nums.length];
        int index = nums.length - 1;
        while (start <= end) {
            int startSquare = nums[start] * nums[start];
            int endSquare = nums[end] * nums[end];
            if (startSquare > endSquare) {
                sortedSquareNums[index] = startSquare;
                start++;
            } else {
                sortedSquareNums[index] = endSquare;
                end--;
            }
            index--;
        }
        return sortedSquareNums;
    }

前提是数组是非递减的，如果是乱序的，此方案行不通