双指针系列-数组篇(LeetCode 27，26，283，844，977)

E 27.移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解题思路1是利用双指针，首尾指针，从首指针开始遍历，若首指针是val，则尾指针位置的值赋值，尾指针动而首指针不动，是为了下一次要比较前一次尾指针的赋值是否为val，不是val则首指针向右移动。这里尾指针赋值为len，时间复杂度为O(n)，空间复杂度为O(1)

思路2是双指针均从首处开始，但是这里会出现非val值的重复赋值

class Solution {
    public int removeElement(int[] nums, int val) {//双指针思路,首尾指针，重合时跳出
//这里注意处理尾处指针是否为val值,这里未保留移除后原数组的顺序，若需保留则可以首首双指针
        //单元素或空元素处理
        int len = nums.length;
        int left = 0;
        int right = len;//这里赋值len则无需比较len=1的特殊情况
//len == 1 && nums[len - 1] == val,且right-1==left处的值也比较了，例如[3,3]示例
        while(left < right){
            if(nums[left] == val){
                nums[left] = nums[right - 1];
                right--;//不对首指针进行处理，下一次就可以判断尾指针的赋值是否为val
            }
            else
                left++;
        }
        return left;
    }//这个只遍历一遍
}

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

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

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

解题思路是双指针left和right在首首处开始，找到第一个不与left指针相同数值的right指针位置的数赋值，注意先left+1再赋值，因为还需每个元素出现1次，时间复杂度为O(n)，空间复杂度为O(1)

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0 || nums == null)
            return 0;
        int left = 0;
        for(int right = 1; right < nums.length; right++){
            if(nums[left] != nums[right]){
                left++;  
                nums[left] = nums[right];                   
                }     
            }                 
        return left + 1;
    }
}

E 283.移动零

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

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

解题思路是利用双指针left，right首首开始，当right指针不为0时，则赋值给left指针，right指针处附0，其实也是交换的意思，无需对left指针进行判断，因为均从首首开始，所以right指针就包含了left指针的判断。时间复杂度为O(n)，空间复杂度为O(1)

class Solution {
    public void moveZeroes(int[] nums) {
 
        int left = 0;
        int right = 0;
        while(right < nums.length){
            if(nums[right] != 0){
                if(right > left){
                    nums[left] = nums[right];                  
                    nums[right] = 0; //也是做交换的意思
                }
                left++;
            }       
            right++;           
        }
//这个题我是赋值处理方法，我的误区就是一直在right位置是否为0处怎么好移动left和right，
//后面自己附0的方法其实跟交换思想有异曲同工之处，但是我一直在纠结left=0和right=0，
//其实只要考虑right就行，因为right是有left那里过去的，既然left没动，说明left处就为0，动了才前进+1
    }

E 844.比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

该题使用双指针的思路解决，时间复杂度为O(n + m)，空间复杂度是O(1)，此外还可以借助栈来实线，时间复杂度为O(n + m)，空间复杂度是O(n + m)，总体思路是逐步消除'#'的影响后再来比较字符，此题中只有'#'左边的字符会消除，所以考虑借助指针尾处开始，使用另一个指针skip来记录删除字符的情况，遇到'#'需增加删除字符个数，skip+1，遇到其他字符skip-1代表删除该字符，然后均左移，直到遇到无'#'影响的字符才跳出比较

class Solution {
    public boolean backspaceCompare(String s, String t) {
        //空间复杂度需为O(1),栈的方法空间复杂度为O(n)
        //'#'只对左边字符有影响所以从逆序开始遍历，使用Skip来处理'#'的影响
        //遇到'#'说明需要删除一个字符skip+1，遇到非'#'且skip不为0，则代表删除该字符，skip-1，    
        //处理好'#'的影响后，我们再来比较字符串
        int i = s.length() - 1;
        int j = t.length() - 1;
        int skipS = 0, skipT = 0;
        /*
        char[] s = S.toCharArray();转换为字符数组的方式
        char[] t = T.toCharArray();
        */
        while(i >= 0 || j >= 0){//一方出界才结束循环
            //处理'#'对s的影响，即寻找第一个可以比较的字符位置
            while(i >= 0){
                if(s.charAt(i) == '#'){//需增加删除字符，skipS增加，继续左移
                    skipS++;
                    i--;
                }
                else if(skipS > 0){//该位置字符仍需删除，删除后skipS减少，继续左移
                    skipS--;
                    i--;
                }
                else//既不等于'#'又skipS为0，则此时该位置字符无需删除可以作比较，跳出循环
                    break;
            }
 
            //与String s同理
            while(j >= 0){
                if(t.charAt(j) == '#'){
                    skipT++;
                    j--;
                }
                else if(skipT > 0){
                    skipT--;
                    j--;
                }
                else
                    break;
            }
 
            //下面开始比较，考虑false的几种情况
            //一方出界i >= 0, j < 0; j >= 0, i < 0
            //均未出界i >= 0, j >= 0，但当前字符不同s[i] != t[j];
            if(i >= 0 && j >= 0){
                if(s.charAt(i) != t.charAt(j))
                    return false;
            }                
            else if(i >= 0 || j >= 0)
                return false;
            //注意这里不在之后使用else，会超出时间限制
            //因为如果进入到前面的if里则到不了这里的--操作，实际上未return还需继续遍历
            i--;
            j--;  
        }
        return true;
    }   
}

E 977.有序数组的平方

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

1.双指针+归并排序思想 

利用原数组有序的条件，找到负数与非负数的分界点，然后利用双指针在分界点处两边进行比较，选择较小的值填充入新结果数组，若有一指针到达分界点，进另一指针依次向边界点移动填充结果，时间复杂度是O(n)，不算上新数组开辟的空间则空间复杂度是O(1)

class Solution {
    public int[] sortedSquares(int[] nums) {
       //官方双指针解法1，解题思路是找到负数与非负数的分界点，利用其单调性进行解题
       //首先找出这个分界点
       int neg = -1;
       for(int i = 0; i < nums.length; i++){
           if(nums[i] < 0){
               neg = i;
           }
           else   
                break;//找到第一个非负数的位置则跳出，neg位置为负数，neg + 1为非负数             
       }
        //分界点左边平方后单调递减，右边单调递增，移动两指针顺序放入结果数组中
        int[] sqr = new int[nums.length];
        int left = neg;
        int right = neg + 1;
        int index = 0;
        while(left >= 0 || right < nums.length){
            if(left < 0){
                sqr[index] = nums[right] * nums[right];
                right++;
            }//说明全是非负数，直接顺序放入即可
            else if(right == nums.length){
                sqr[index] = nums[left] * nums[left];
                left--;
            }//说明全是负数，left指针逆序顺序放入即可
            else if(nums[left] * nums[left] > nums[right] * nums[right]){
                sqr[index] = nums[right] * nums[right];
                right++;
            }//比较放入小的
            else{
                sqr[index] = nums[left] * nums[left];
                left--;
            }
            index++;
        }
        return sqr;
    }
}

2.首尾双指针比较

首尾指针比较，若值较大者则放入新数组中，逆序填充，时间复杂度是O(n)，不算上新数组开辟的空间则空间复杂度是O(1)

class Solution {
    public int[] sortedSquares(int[] nums) {
       //官方双指针解法2，解题思路是首尾指针比较，较大的值逆序填充结果数组
       int[] sqr = new int[nums.length];
       int left = 0;
       int right = nums.length - 1;
       int index = nums.length - 1;//逆序填充
       while(left <= right){//注意left=right处也要比较
           if(nums[left] * nums[left] > nums[right] * nums[right]){
               sqr[index] = nums[left] * nums[left];
               left++;
           }
           else{
               sqr[index] = nums[right] * nums[right];
               right--;
           }
           index--;
       }       
        return sqr;
    }
}