双指针（牛客）

题目来自牛客题目库 算法篇面试必刷TOP101。

BM87 合并两个有序的数组(简单)

题目

题目链接

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

数据范围：0≤n,m≤100，∣A~i~∣<=100，∣B~i~∣<=100

注意：

1. 保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n

2. 不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印

3. A 数组在[0,m-1]的范围也是有序的

示例：

示例1：
输入：[4,5,6],[1,2,3]
返回值：[1,2,3,4,5,6]
说明：A数组为[4,5,6]，B数组为[1,2,3]，后台程序会预先将A扩容为[4,5,6,0,0,0]，B还是为[1,2,3]，m=3，n=3，传入到函数merge里面，然后请同学完成merge函数，将B的数据合并A里面，最后后台程序输出A数组  
示例2：
输入：[1,2,3],[2,5,6]
返回值：[1,2,2,3,5,6]

解法 双指针

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        //指向数组A的结尾
        int i = m - 1;
        //指向数组B的结尾
        int j = n - 1;
        //指向数组A空间的结尾处
        int k = m + n - 1;
        //从两个数组最大的元素开始，直到某一个数组遍历完
        while (i >= 0 && j >= 0) {
            //将较大的元素放到最后
            if (A[i] > B[j])
                A[k--] = A[i--];
            else
                A[k--] = B[j--];
        }
        //数组A遍历完了，数组B还有，则还需要添加到数组A前面
        while (j >= 0)
            A[k--] = B[j--];
        //数组B遍历完了，数组A前面正好有，不用再添加
    }
}

BM88 判断是否为回文字符串(入门)

题目

题目链接

给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。

字符串回文指该字符串正序与其逆序逐字符一致。

数据范围：0<n≤1000000

要求：空间复杂度 O(1) ，时间复杂度 O(n)

示例略。

解法 双指针

import java.util.*;
public class Solution {
    public boolean judge (String str) {
        //首指针
        int left = 0; 
        //尾指针
        int right = str.length() - 1;
        //首尾往中间靠  
        while(left < right){  
            //比较前后是否相同
            if(str.charAt(left) != str.charAt(right)) 
                return false;
            left++;
            right--;
        }
        return true;
    }
}

BM89 合并区间(中等)

题目

题目链接

给出一组区间，请合并所有重叠的区间。

请保证合并后的区间按区间起点升序排列。

数据范围：区间组数 0≤n≤2×10^5^，区间内 的值都满足 0≤val≤2×10^5^

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

进阶：空间复杂度 O(val)，时间复杂度 O(val)

示例：

示例1：
输入：[[10,30],[20,60],[80,100],[150,180]]
返回值：[[10,60],[80,100],[150,180]]
示例2：
输入：[[0,10],[10,20]]
返回值：[[0,20]]

解法 贪心

• step 1：既然要求重叠后的区间按照起点位置升序排列，我们就将所有区间按照起点位置先进行排序。使用sort函数进行排序，重载比较方式为比较interval结构的start变量。
• step 2：排序后的第一个区间一定是起点值最小的区间，我们将其计入返回数组res，然后遍历后续区间。
• step 3：后续遍历过程中，如果遇到起点值小于res中最后一个区间的末尾值的情况，那一定是重叠，取二者最大末尾值更新res中最后一个区间即可。
• step 4：如果遇到起点值大于res中最后一个区间的末尾值的情况，那一定没有重叠，后续也不会有这个末尾的重叠区间了，因为后面的起点只会更大，因此可以将它加入res。

import java.util.*;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        //去除特殊情况
        if (intervals.size() == 0)
            return res;
        //重载比较，按照区间首排序
        Collections.sort(intervals, (o1, o2) -> o1.start - o2.start);
        //放入第一个区间
        res.add(intervals.get(0));
        int count = 0;
        //遍历后续区间，查看是否与末尾有重叠
        for (int i = 1; i < intervals.size(); i++) {
            Interval o1 = intervals.get(i);
            Interval origin = res.get(count);
            if (o1.start > origin.end) {
                //区间没有重叠，直接向res中添加区间
                res.add(o1);
                count++;
                
            } else {
                //区间有重叠，更新结尾
                res.remove(count);
                Interval s = new Interval(origin.start, o1.end);
                if (o1.end < origin.end)
                    s.end = origin.end;
                res.add(s);
            }
        }
        return res;
    }
}

BM90 最小覆盖子串(较难)

题目

题目链接

给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。

数据范围：0≤∣S∣,∣T∣≤10000，保证s和t字符串中仅包含大小写英文字母

要求：进阶：空间复杂度 O(n)， 时间复杂度 O(n)

例如：

S = “XDOYEZODEYXNZ”

T = “XYZ”

找出的最短子串为”YXNZ”

注意：

如果 s 中没有包含 t 中所有字符的子串，返回空字符串 “”；

满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。

示例：

示例1：
输入："XDOYEZODEYXNZ","XYZ"
返回值："YXNZ"
示例2：
输入："abcAbA","AA"
返回值："AbA"

解法 哈希、双指针

• step 1：建立哈希表，遍历字符串T，统计各个字符出现的频率，频率计为负数。
• step 2：依次遍历字符串S，如果匹配则将哈希表中的相应的字符加1。
• step 3：在遍历过程中维护一个窗口，如果哈希表中所有元素都大于0，意味着已经找全了，则窗口收缩向左移动，找最小的窗口，如果不满足这个条件则窗口右移继续匹配。窗口移动的时候需要更新最小窗口，以取得最短子串。
• step 4：如果匹配到最后，窗口left（初始为-1）也没有右移，说明没有找到，返回空串即可。
• step 5：最后使用字符串截取函数，截取刚刚记录下的窗口即可得到符合条件的最短子串。

import java.util.*;
public class Solution {
    //检查是否有小于0的
    boolean check(int[] hash) { 
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] < 0)
                return false;
        }
        return true;
    };
    
    public String minWindow (String S, String T) {
        // 初始化窗口大小
        int cnt = S.length() + 1;
        //记录目标字符串T的字符个数
        int[] hash = new int[128]; 
        for(int i = 0; i < T.length(); i++)
        	//初始化哈希表，含有目标值就减1，找的时候再加1
            hash[T.charAt(i)] -= 1; 
        // slow和fast是遍历字符串的快慢指针
        int slow = 0, fast = 0;  
        // left和right是窗口的左右区间端点
        int left = -1, right = -1;  
        for(; fast < S.length(); fast++){
            char c = S.charAt(fast);
            //目标字符匹配+1
            hash[c]++;
            //没有小于0的说明都覆盖了，缩小窗口
            while(check(hash)){  
                //取最优解
                if(cnt > fast - slow + 1){ 
                    cnt = fast - slow + 1;  
                    left = slow;
                    right = fast;
                }
                c = S.charAt(slow);
                //缩小窗口的时候减1
                hash[c]--; 
                //窗口缩小
                slow++;      
            }
        }
        //找不到的情况
        if(left == -1)
            return "";
        return S.substring(left, right + 1);
    }
}

BM91 反转字符串(入门)

题目

题目链接

写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

数据范围：0≤n≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n)

示例：

示例1：
输入："abcd"
返回值："dcba"
示例2：
输入：""
返回值：""

解法 双指针

import java.util.*;
public class Solution {
    public String solve (String str) {
        char[] cstr = str.toCharArray();
        int len = str.length();
        for (int i = 0 ; i < len / 2 ; i++) {
            char t = cstr[i];
            cstr[i] = cstr[len - 1 - i];
            cstr[len - 1 - i] = t;
        }
        return new String(cstr);
    }
}

注意字符串和字符数组之间的转换。

BM92 最长无重复子数组(中等)

题目

题目链接

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。

子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

数据范围：0≤ arr.length ≤105，0<arr[i]≤10^5^

示例：

示例1：
输入：[2,3,4,5]
返回值：4
说明：[2,3,4,5]是最长子数组 
示例2：
输入：[2,2,3,4,3]
返回值：3
说明：[2,3,4]是最长子数组 
示例3：
输入：[9]
返回值：1
示例4：
输入：[1,2,3,1,2,3,2,2]
返回值：3
说明：最长子数组为[1,2,3] 

解法1 队列

我们可以用一个队列，把元素不停的加入到队列中，如果有相同的元素，就把队首的元素移除，这样我们就可以保证队列中永远都没有重复的元素。

核心方法：Boolean queue.contains(a)：判断队列中是否含有元素a

import java.util.*;

public class Solution {

    public int maxLength(int[] arr) {
        //用链表实现队列，队列是先进先出的
        Queue<Integer> queue = new LinkedList<>();
        int res = 0;
        for (int c : arr) {
            while (queue.contains(c)) {
                //如果有重复的，队头出队
                queue.poll();
            }
            //添加到队尾
            queue.add(c);
            res = Math.max(res, queue.size());
        }
        return res;
    }
}

解法2 哈希、双指针

import java.util.*;
public class Solution {
    public int maxLength (int[] arr) {
        //哈希表记录窗口内非重复的数字
        HashMap<Integer, Integer> mp = new HashMap<>(); 
        int res = 0;
        //设置窗口左右边界
        for(int left = 0, right = 0; right < arr.length; right++){ 
            //窗口右移进入哈希表统计出现次数
            if(mp.containsKey(arr[right]))
                mp.put(arr[right],mp.get(arr[right])+1); 
            else
                mp.put(arr[right],1);
            //出现次数大于1，则窗口内有重复
            while(mp.get(arr[right]) > 1) 
                //窗口右移，同时减去左端数字的出现次数
                mp.put(arr[left],mp.get(arr[left++])-1); 
            //维护子数组长度最大值
            res = Math.max(res, right - left + 1); 
        }
        return res;
    }
}

BM93 盛水最多的容器(中等)

题目

题目链接

给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水

1.你不能倾斜容器

2.当n小于2时，视为不能形成容器，请返回0

3.数据保证能容纳最多的水不会超过整形范围，即不会超过2^31^-1

数据范围:

0<= height.length <=10^5^

0<= height[i] <=10^4^

如输入的height为[1,7,3,2,4,5,8,2,7]，那么如下图:

示例：

示例1：
输入：[1,7,3,2,4,5,8,2,7]
返回值：49
示例2：
输入：[2,2]
返回值：2
示例3：
输入：[5,4,3,2,1,5]
返回值：25

解法 双指针、贪心

import java.util.*;
public class Solution {
    public int maxArea (int[] height) {
        //排除不能形成容器的情况
        if(height.length < 2) 
            return 0;
        int res = 0; 
        //双指针左右界
        int left = 0; 
        int right = height.length - 1;
        //共同遍历完所有的数组
        while(left < right){ 
            //计算区域水容量
            int capacity = Math.min(height[left], height[right]) * (right - left); 
            //维护最大值
            res = Math.max(res, capacity); 
            //优先舍弃较短的边
            if(height[left] < height[right]) 
                left++;
            else
                right--;
         }
        return res;
    }
}

BM94 接雨水问题(较难)

题目

题目链接

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

数据范围：数组长度 0≤n≤2×10^5^，数组中每个值满足 0<val≤10^9^ ，保证返回结果满足 0≤val≤10^9^

要求：时间复杂度 O(n)

示例：

示例1：
输入：[3,1,2,5,2,4]  
返回值：5 
说明：数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。
示例2：
输入：[4,5,1,3,2]
返回值：2 

解法 双指针

• step 1：检查数组是否为空的特殊情况
• step 2：准备双指针，分别指向数组首尾元素，代表最初的两个边界
• step 3：指针往中间遍历，遇到更低柱子就是底，用较短的边界减去底就是这一列的接水量，遇到更高的柱子就是新的边界，更新边界大小。

import java.util.*;
public class Solution {
    public long maxWater (int[] arr) {
        //排除空数组
        if(arr.length == 0) 
            return 0;
        long res = 0;
        //左右双指针
        int left = 0; 
        int right = arr.length - 1; 
        //中间区域的边界高度
        int maxL = 0; 
        int maxR = 0;
        //直到左右指针相遇
        while(left < right){ 
            //每次维护往中间的最大边界
            maxL = Math.max(maxL, arr[left]); 
            maxR = Math.max(maxR, arr[right]);
            //较短的边界确定该格子的水量
            if(maxR > maxL) 
                res += maxL - arr[left++]; 
            else
                res += maxR - arr[right--];
        }
        return res;
    }
}

总结

• 双指针往往是同向的快慢指针或从两端向中间的左右指针。
• 有时与哈希表一起使用解题。