【LeetCode】数组问题：对撞指针

忘是亡心i 2022-10-29 09:11 163阅读 0赞

### 对撞指针 ###

核心思想

*  维护两个索引
    
     *  一个指针开始时为 l = 0 ，并且执行的操作为 l ++
     *  一个指针开始时为 r = arr.length - 1,并且执行的操作为 r --；
 *  终止条件是 while( l < r )
    
     *  跳出循环的结果会是 l = r

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

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。
    你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
    输出: [1,2]
    解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

**法一：暴力，双重循环**

略

**法二：遍历 + 二分， O ( n l o g n ) O(nlogn) O(nlogn)**

class Solution { 
        public int[] twoSum(int[] numbers, int target) { 
            for(int i = 0 ; i < numbers.length ; i ++ ){ 
                int find = target - numbers[i];
    
                int l = i + 1 , r = numbers.length - 1;
                int findIdx = -1;
                while(l <= r){ 
                    int mid = (l + r) / 2;
                    if(numbers[mid] == find){ 
                        findIdx = mid;
                        break;
                    }else if(numbers[mid] > find){ 
                        r = mid - 1;
                    }else{ 
                        l = mid + 1;
                    }
                }
    
                if(findIdx != -1){ 
                    return new int[]{ i + 1 , findIdx + 1};
                }
            }
            return null;
        }
    }

**法三：指针碰撞**

class Solution { 
        public int[] twoSum(int[] numbers, int target) { 
            int l = 0 , r = numbers.length - 1;
            while( l < r ){ 
                int now = numbers[l] + numbers[r];
                if(now == target){ 
                    return new int[]{  l + 1, r + 1 };
                }else if(now < target){ 
                    l ++;
                }else{ 
                    r --;
                }
            }
            return null;
        }
    }

#### 125、验证回文串 ####

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
    输出: true示例 2:

示例 2:

输入: "race a car"
    输出: false

**题解**

import java.util.regex.Pattern;
    
    class Solution { 
        public boolean isPalindrome(String s) { 
            char[] chars = s.toCharArray();
            StringBuffer target = new StringBuffer();
            Pattern pattern = Pattern.compile("[a-zA-Z0-9]");
    
            for(char ch : chars){ 
                String chV = String.valueOf(ch);
                if(pattern.matcher(chV).matches()){ 
                    target.append(chV.toLowerCase());
                }
            }
    
            int l = 0 , r = target.length() - 1;
            while( l < r){ 
                if(target.charAt(l ++) != target.charAt(r --)){ 
                    return false;
                }
            }
            return true;
        }
    }

#### 344、反转字符串 ####

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char\[\] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：["h","e","l","l","o"]
    输出：["o","l","l","e","h"]

示例 2：

输入：["H","a","n","n","a","h"]
    输出：["h","a","n","n","a","H"]

**题解**

class Solution { 
        public void reverseString(char[] s) { 
            int l = 0 , r = s.length - 1;
            while( l < r){ 
                char mid = s[l];
                s[l] = s[r];
                s[r] = mid;
    
                l ++;
                r --;
            }
        }
    }

#### 345、反转字符串中的元音字母 ####

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1：

输入："hello"
    输出："holle"示例 2：

输入："leetcode"
    输出："leotcede"

**题解**

class Solution { 
        public String reverseVowels(String s) { 
            int l = 0 , r = s.length() - 1;
            char[] sArr = s.toCharArray();
            String contain = "aeiouAEIOU";
            
            while(l < r){ 
                while(!contain.contains(String.valueOf(sArr[l])) && l < r){ 
                    l ++;
                }
                while(!contain.contains(String.valueOf(sArr[r])) && l < r){ 
                    r --;
                }
                if(l == r){ 
                    break;
                }
                char mid = sArr[l];
                sArr[l ++] = sArr[r];
                sArr[r --] = mid;
            }
            return new String(sArr);
        }
    }

#### [11. 盛最多水的容器][11.] ####

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

**题解**

法一：暴力

class Solution { 
        public int maxArea(int[] height) { 
            int max = 0;
            for(int i = 0 ; i < height.length ; i ++){ 
                for(int j = i + 1 ; j < height.length ; j ++){ 
                    int h = height[i] <= height[j] ? height[i] : height[j];
                    int full = (j - i) * h;
                    max = max > full ? max : full;
                }
            }
            return max;
        }
    }

**法二：碰撞指针**

*  因为暴力有许多无效的移动（即在该种移动下面积肯定是减小的）
 *  碰撞指针（即从两边开始相向遍历），就是为了消除无效的遍历，让两边中较小的边移动，这样 s 才有可能是变大

class Solution { 
        public int maxArea(int[] height) { 
            int l = 0 , r = height.length - 1;
            int s = 0;
            while(l < r){ 
                int newS = (r - l) * (height[l] > height[r] ? height[r] : height[l]);
                s = s > newS ? s : newS;
                if(height[l] < height[r]){ 
                    l ++;
                }else { 
                    r --;
                }
            }
            return s;
        }
    }

[11.]: https://leetcode-cn.com/problems/container-with-most-water/