双指针的妙用

一.1.双指针思想

所谓的双指针其实就是两个变量,不一定真的是指针。

在数组的翻转,以及去重中双指针思想有很大的解题帮助

看个例子,从下面序列中删除重复元素[1,2,2,2,3,3,3,5,5,7,8],重复元素只保留一个。删除之后的结果应该为[1,2,3,5,7,8]。我们可以在删除第一个2时将将其后面的元素整体向前移动一次,删除第二个2时再将其后的元素整体向前移动一次,处理后面的3和5都一样的情况,这就导致我们需要执行5次大量移动才能完成,效率太低。如果使用双指针可以方便的解决这个问题,如图:

这里是一个经典的双指针快慢指针的思想

image (16)

先我们定义两个指针slow、fast。slow表示当前位置之前的元素都是不重复的,而fast则一直向后找,直到找到与slow位置不一样的 ,找到之后就将slow向后移动一个位置,并将arr[fast]复制给arr[slow],之后fast继续向后找,循环执行。找完之后slow以及之前的元素就都是单一的了。这样就可以只用一轮移动解决问题。

二.删除元素专题

1.移除元素

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

image-20230923210301327

解法一:对撞指针

这种解法和快速排序中的思路比较相似,让两个指针找到各自目标的值后停止,之后进行交换

但是需要这里注意的是需要判断if(nums[left]==val&&nums[right]!=val),因为这样可以确保先交换再进行寻找,否则先找再交换可能会出问题情况会更复杂

image-20230923221037695

这里的思路是slow会留在每一个val值上,fast的值为非val值,将fast的值赋值给slow即可,

class Solution {
    public int removeElement(int[] nums, int val) {
int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            if(nums[left]==val&&nums[right]!=val) {
                int tem = nums[left];
                nums[left] = nums[right];
                nums[right] = tem;
            }
            if (nums[right] == val) {
                right--;
            }
            if (nums[left] != val) {
                left++;
            }


    }return left;
}

解法二:快慢指针进行值的覆盖

这种方法利用了双指针,相当于每一次将慢指针指向的val值,用fast值覆盖

image-20230923223712035

 public static int removeElement(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;
    }

也可以结合两种思路:

左指针不等于val时一直走,如果遇见了val值会停止,将right的值赋值,就算right的值为val,下一场继续对left进行判定,不等于val时,才会继续向前走

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

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

LeetCode26 给你一个有序数组 nums ,请你原地删除重复出现的元素,使每个元素只出现一次 ,返回删除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例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 。不需要考虑数组中超出新长度后面的元素

解法一:双指针:快慢指针

这里的思路是,将slow-1的值和fast进行判断,如果相同,fast继续前进,不同的时候,将fast值赋值给slow,这个时候也就保证了slow的值和slow-1的值一定不一样,也就是完成了保留一个元素,然后将未重复的元素对slow当前元素的覆盖

class Solution {
    public int removeDuplicates(int[] nums) {
    int slow = 1;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow - 1]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

扩展:

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使得出现次数超过两次的元素只出现两次 ,返回删除后数组的新长度。

不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

这里的思路需要改变一下,

1.可以发现上一道题的原理是,通过检索slow前一个,进行保留一个元素,那么这里slow的前两个就行,但是这样就需要考虑越界情况,上一道题不需要考虑越界是因为当长度为1时,slow-1=0.但是这里需要考虑,因为当长度为1时,会发生越界,因此加一个判断nums.length<=2的时候.直接输出就行

2.这里需要将fast的初始值设置为2,因为进行比较的是fast,上道题如果设置fast等于1的初始值,需要再次判断nums长度是否为0,

class Solution {
    public int removeDuplicates(int[] nums) {
    int slow = 2;
    if(nums.length<=2){return nums.length;}
        for (int fast = 2; fast < nums.length; fast++) {
            if (nums[fast] != nums[slow - 2]) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

三.元素奇偶移动专题

给你一个整数数组 nums,将 nums 中的的所有偶数元素移动到数组的前面,后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

示例 1:

输入:nums = [3,1,2,4]
输出:[2,4,3,1]
解释:[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。
示例 2:

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

解法一:双指针

思路类似上面的移除元素的双指针对撞,但是有一点优化的地方值得注意,当数组不满足要求的时候,左边的数一定是偶数,此时只需要比较左右指针指的数左边的余数大于右边余数的时候,交换

 int left = 0;
        int right = nums.length-1;
        while (left<=right){
            if(nums[left]%2!=0&&nums[right]%2==0){
                int tem = nums[left];
                nums[left] = nums[right];
                nums[right] = tem;

            }
            if(nums[left]%2==0){
                left++;
            }
            if(nums[right]%2!=0){
                right--;
            }

        }return nums;

解法二:仿冒泡排序

冒泡的思想是每一次让一个最大或者最小的数到数组的最前或者最后,那么这里就可以让任意一个偶数与奇数之间的交换,就可以达到目的

class Solution {
    public int[] sortArrayByParity(int[] nums) {
       for (int i = 0; i < nums.length-1; i++) {
            for (int j = 0; j < nums.length-1-i; j++) {
                if(nums[j]%2!=0&&nums[j+1]%2==0){
                    int tem = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = tem;
                }
            }
        }return nums;


    }
}

四.数组轮转问题

先看题目要求,LeetCode189.给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

例如:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

方法一:通过数组的复制得

  k =k% nums.length;
        int newArr[] = new int[nums.length];
        System.arraycopy(nums,0,newArr,k,newArr.length-k);
        System.arraycopy(nums,newArr.length-k,newArr,0,k);

        System.arraycopy(newArr,0,nums,0,newArr.length);

方法二:翻转

因为需要让数字到左边,因此可以先整体翻转,然后翻转k以前的,以及k到数组的最后

  k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

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

五.数组的区间专题

数组中表示的数据可能是连续的,也可能是不连续的,如果将连续的空间标记成一个区间,那么我们可以再造几道题,先看一个例子:
LeetCode228.给定一个无重复元素的有序整数数组nums。返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。列表中的每个区间范围 [a,b] 应该按如下格式输出:"a->b" ,如果 a != b"a" ,如果 a == b

这道题思路是双指针,用fast+1和fast值进行比较,用slow进行对点fast的标记,以及需要注意的一点,在slow移动到fast+1处的时候,不能改变fast的值,fast的值必须要在循环中相加,因为多加一次会导致fast+1与fast跳过一个数字

class Solution {
    public List<String> summaryRanges(int[] nums) {
 int slow = 0;
        List<String>list = new ArrayList<>();
        for (int fast=0; fast < nums.length; fast++) {

            if(fast + 1 == nums.length || nums[fast] + 1 != nums[fast + 1]){

                if(fast!=slow){
                   String  s= nums[slow] + "->" + nums[fast];
                    list.add(s);
                }else {
                    list.add(Integer.toString(nums[fast]));
                }


                    slow = fast+1;


            }
        }return list;
    }
}

六.字符串替换空格问题

这是剑指offer中的题目,出现频率也很高:请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
首先要考虑用什么来存储字符串,如果是长度不可变的char数组,那么必须新申请一个更大的空间。如果使用长度可变的空间来管理原始数组,或者原始数组申请得足够大,这时候就可能要求你不能申请O(n)大小的空间,我们一个个看。

public  String replaceSpace(StringBuffer str) {
    if (str == null)
        return null;
    int numOfblank = 0;//空格数量
    int len = str.length();
    for (int i = 0; i < len; i++) {  //计算空格数量
        if (str.charAt(i) == ' ')
            numOfblank++;
    }
    str.setLength(len + 2 * numOfblank); //设置长度
    int fast = len - 1;  //两个指针
    int slow = (len + 2 * numOfblank) - 1;
    
    while (fast >= 0 && slow > fast) {
        char c = str.charAt(fast);
        if (c == ' ') {
            fast--;
            str.setCharAt(slow--, '0');
            str.setCharAt(slow--, '2');
            str.setCharAt(slow--, '%');
        } else {
            str.setCharAt(slow, c);
            fast--;
            slow--;
        }
    }
    return str.toString();
}