数组相向指针系列

目录

977. 有序数组的平方

27. 移除元素

941. 有效的山脉数组 

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

344. 反转字符串

5. 最长回文子串

---

977. 有序数组的平方

977. 有序数组的平方

思路：

• 前后指针
• 两个指针分别平方，谁大放到一个新数组的最后然后依次往前，两指针相向而行
• 注意不要将结果拷回原数组，这样就会对新放入元素进行平方导致结果错误

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

27. 移除元素

27. 移除元素

思路：

• 使用前后指针->两个指针相向走
• 前指针用来维护新的数组
• 后指针寻找非val元素,前指针寻找val元素，然后将后指针指向的元素赋值给前指针指向的元素,赋值之后两指针都要进行相向移动
• 注意点:这里是left<=right，一定是两指针错开，left前面就是我们维护的新数组，left就是数组长度

941. 有效的山脉数组 

941. 有效的山脉数组

思路：相向指针

• 定义两个指针分别定义在数组的前后
• left满足arr[left]<arr[left-1]，right满足arr[right-1]>arr[right]  并且left+1和right-1要注意边界问题不能越界
• 最终left和right都指向各自不合法的位置此时两者刚好相遇证明是有效的山脉就一个山峰
• 注意不能是单调的也就是left和right有一个是不动的  不可能是山脉

class Solution {
    public boolean validMountainArray(int[] arr) {
        if(arr.length<3){
            return false;
        }
         int left =0;
         int right = arr.length-1;
         while(left+1<arr.length&&arr[left]<arr[left+1]){
             left++;
         }
         while(right-1>0&&arr[right-1]>arr[right]){
             right--;
         }
         //此时left和right都走到了相应不合法的位置
         //不能是单调的并且left和right是相遇的证明是山脉
         if(left!=0&&right!=arr.length-1&&left==right){
               return true;
         }
         return false;
    }
}

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

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

相向指针

• 1.两指针指向的元素之和大于target，因为数组是递增有序的，所以说明右指针指向的元素过大，调整右指针
• 2.两指针指向的元素之和小于target，因为数组是递增有序的，所以说明左指针指向的元素过小，调整左指针

class Solution {
    public int[] twoSum(int[] numbers, int target) {
         int[] tmp = new int[2];
         int left =0;
         int right = numbers.length-1;
         while(left<right){
             if(numbers[left]+numbers[right]>target){//调整右指针
                right--;
             }else if(numbers[left]+numbers[right]<target){//调整左指针
                 left++;
             }else {//相等 处理返回值
                tmp[0] = left+1; 
                tmp[1] = right+1;
                break;
             }
         }
         return tmp;
    }
}

344. 反转字符串

344. 反转字符串

思路：

• 左右指针相向而行，交换两个字符即可

class Solution {
    public void reverseString(char[] s) {
         int left = 0;
         int right = s.length -1;
         while(left<right){
             char tmp = s[left];
             s[left] = s[right];
             s[right] = tmp;
             left++;
             right--;
         }
    }
}

5. 最长回文子串

5. 最长回文子串

思路：

• 采用中间扩散法 两指针相背而行来判断是否回文
• 回文子串有两种情况一种是以一个元素为中心，一种是以两个元素为中心
• 返回子串最长的即可，每次长度都要进行更新

class Solution {
    //找回文子串并且返回回文子串
    public String PalindromeS(String s,int l,int r){
        //采用两指针相背而行，属于中间扩散型适用于回文
        //两指针不能越界并且判断指针指向的字符是否相等
        while(l>=0&&r<=s.length()-1&&s.charAt(l)==s.charAt(r)){
            l--;
            r++;
        }
        return s.substring(l+1,r);//注意substring是左闭右开
    }
    public String longestPalindrome(String s) {
        String s1 = "";
        String s2 = "";
        String res = "";
  
        for(int i =0;i<s.length();++i){
            s1 = PalindromeS(s,i,i);//以一个元素为中心找回文子串eg:ab c ba
            res = s1.length()>res.length()?s1:res;//选择长度最大的返回
            s2 = PalindromeS(s,i,i+1);//以两个元素为中心找回文子串eg:a bb a
            res = s2.length()>res.length()?s2:res;//选择长度最大的返回
        }
        return res;
    }
}