15数据结构与算法刷题之【双指针】篇

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：

2、剑指offerII：

力扣总记录数：

加油加油！

剑指offer

剑指 Offer II 018. 有效的回文【简单】

题目链接： 剑指 Offer II 018. 有效的回文

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

思路：双指针判断法

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            while (i < s.length() && !isSatisfy(s.charAt(i))) {
                i++;
            }
            while (j >= 0 && !isSatisfy(s.charAt(j))) {
                j--;
            }
            if (i >= j) {
                break;
            }
            if (transfer(s.charAt(i++)) != transfer(s.charAt(j--))) {
                return false;
            }
        }
        return true;
    }
    public boolean isSatisfy(char ch) {
        if ((ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {
            return true;
        }
        return false;
    }
    public char transfer(char ch) {
        if (ch >= 'A' && ch <= 'Z') {
            return (char)(ch + 32);
        }
        return ch;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面【简单】

题目链接：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题目内容：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

思路：

1、双指针，从左右两端开始。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
    //1234
    //12345
    public int[] exchange(int[] nums) {
        int n = nums.length;
        int left = 0, right = nums.length - 1;
        while (left < right) {
            while (left < right && nums[left] % 2 == 1) {
                left++;
            }
            while (left < right && nums[right] % 2 == 0) {
                right--;
            }
            //若是成立那么就兑换
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

剑指 Offer 57 - II. 和为s的连续正数序列【简单】

题目链接：剑指 Offer 57 - II. 和为s的连续正数序列

题目内容：输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

思路：

1、滑动窗口

复杂度分析：

• 时间复杂度：O(n)，最大为2n。
• 空间复杂度：O(1)

class Solution {

    //滑动窗口
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        //指定一个区间
        for (int l = 1, r = 1, sum = 0; r < target; r++) {
            sum += r;
            //若是>当前的窗口，及时进行缩减窗口
            while (l < r && sum > target) {
                sum -= l++;
            }
            //若是当前窗口符合
            if (sum == target && r - l > 0) {
                int [] res = new int[r - l + 1];
                for (int i = l; i <= r; i++) {
                    res[i - l] = i;
                }
                list.add(res);
            }
        }
        //将list转换为int数组
        int[][] res = new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

剑指 Offer 48. 最长不含重复字符的子字符串【中等】

题目链接：剑指 Offer 48. 最长不含重复字符的子字符串

题目内容：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

思路：

1、滑动窗口+哈希表

复杂度分析：时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //哈希+滑动窗口
        Set<Character> set = new HashSet<>();
        char[] arr = s.toCharArray();
        int max = 0;
        for (int l = 0, r = 0; r < arr.length; r++) {
            //缩减窗口
            while (l < r && !set.isEmpty() && set.contains(arr[r])) {
                set.remove(arr[l]);//先进行移除再左指针移动
                l++;
            }
            set.add(arr[r]);
            max = Math.max(max, r - l + 1);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

优化一下，对于set集合我们可以使用int数组来替代【最优】：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //哈希+滑动窗口
        int[] buckets = new int[128];
        char[] arr = s.toCharArray();
        int max = 0;
        for (int l = 0, r = 0; r < arr.length; r++) {
            //缩减窗口
            while (l < r && buckets[arr[r]] > 0) {
                buckets[arr[l]]--;
                l++;
            }
            buckets[arr[r]]++;
            max = Math.max(max, r - l + 1);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

牛客网

合并两个有序的数组【简单】

题目链接：合并两个有序的数组

题目内容：给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组。

思路1：合并数组。从大到小，针对A数组来从后往前填。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[k--] = A[i--];
            }else {
                A[k--] = B[j--];
            }
        }
        //若是B还有剩余继续往前添加，若是B没有，那就直接结束了
        while (j >= 0) {
            A[k--] = B[j--];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

反转字符串【简单】

题目链接：反转字符串

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

思路：双指针来进行交换替换字符。

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

import java.util.*;

public class Solution {
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    public String solve (String str) {
        int i = 0, j = str.length() - 1;
        char[] chars = str.toCharArray();
        while (i < j) {
            char temp = chars[i];
            chars[i] = chars[j];
            chars[j] = temp;
            i++;
            j--;
        }
        return new String(chars);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

判断是否为回文字符串【中等】

题目链接：合并两个有序的数组

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

思路1：使用双指针，一个从前开始，一个从后开始来进行遍历比较。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param str string字符串 待判断的字符串
     * @return bool布尔型
     */
    public boolean judge (String str) {
        int i = 0, j = str.length() - 1;
        while (i <= j) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最长无重复子数组【中等】

题目链接：最长无重复子数组

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

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

思路：滑动窗口。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

import java.util.*;


public class Solution {
    /**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int maxLength (int[] arr) {
        //滑动窗口
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int left = 0, right = 0; right < arr.length; right++) {
            //这个if操作就是往map里面添加值的
            if (map.containsKey(arr[right])) {
                map.put(arr[right], map.get(arr[right]) + 1);
            }else {
                map.put(arr[right], 1);
            }
            //移动left指针
            while (map.get(arr[right]) > 1) {
                map.put(arr[left], map.get(arr[left++]) - 1);
            }
            //计算长度最大值
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

盛水最多的容器【中等】

题目链接：盛水最多的容器

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

思路：定义左右指针，然后不断的缩短容量，移动位置。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型一维数组 
     * @return int整型
     */
    public int maxArea (int[] height) {
        int res = 0;
        int left = 0, right = height.length - 1;
        while (left < right) {
            //贪心策略
            res = Math.max(res, Math.min(height[left], height[right]) * (right - left));
            //如果左边的高度<右边的高度，那么左边位置向右移动
            if (height[left] < height[right]) {
                left++;
            }else{
                right--;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

接雨水问题【中等】

题目链接：接雨水问题

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

思路1：双指针方案。定义左右各个最大高度，然后来进行比较平移，若是右边更高，那么就开始平移左边的并且进行计算。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        int i = 0, j = arr.length - 1;
        int maxL = 0;
        int maxR = 0;
        long res = 0;
        while (i < j) {
            //取出当前左右边最大的边界
            maxL = Math.max(maxL, arr[i]);
            maxR = Math.max(maxR, arr[j]);
            //若是右边>左边，移动左边位置
            if (maxR > maxL) {
                res += maxL - arr[i++];
            }else {
                res += maxR - arr[j--];
            }
        }
        return res;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

合并区间【中等】

题目链接：合并区间

题目内容：给出一组区间，请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。

思路：排序比较。①根据start来进行排序。②不断的进行判断star<=新添加集合中元素的end，就可以直接添加进去。

复杂度分析：

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

import java.util.*;
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if (intervals == null || intervals.size() == 0 || intervals.size() == 1) {
            return intervals;
        }
        //1、先对集合中的所有元素根据start来进行排序
        Collections.sort(intervals, (o1, o2)->o1.start - o2.start);
        //2、不断的拿intervals中的start来与list最后一个end来比较
        ArrayList<Interval> list = new ArrayList<>();
        list.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals.get(i).start <= list.get(list.size() - 1).end) {
                //list.get(list.size() - 1).end = intervals.get(i).end;
                //优化：针对[[1,4],[2,3]]，所以需要进行比较
                list.get(list.size() - 1).end = Math.max(intervals.get(i).end, list.get(list.size() - 1).end);
            }else {
                list.add(intervals.get(i));
            }
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

最小覆盖子串【中等】

题目链接：最小覆盖子串

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

思路1：滑动窗口，先不断的进行窗口扩大，满足条件之后进行缩减，然后不断的使用两个指针进行移动比较。

复杂度分析：

• 时间复杂度：O(n*m)
• 空间复杂度：O(1)

import java.util.*;


public class Solution {
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    //滑动窗口
    public String minWindow (String S, String T) {
        //使用一个hash表，index下标表示对应的字符，value表示出现的次数，初始为0，若是有两个就是-2
        int[] hash = new int[128];
        for (int i = 0; i < T.length(); i++) {
            //可能会有重复的字符
            hash[T.charAt(i)]--;
        }
        //快慢指针来进行移动的
        int slow = 0, fast = 0;
        //左右指针用来记录最小子串的左右位置
        int left = -1, right = -1;
        //记录最小长度
        int min = S.length() + 1;
        for (;fast < S.length(); fast++) {
            //对字符所在位置下标+1
            hash[S.charAt(fast)]++;
            //如果当前已经覆盖所有的字符，那么进行缩减当前的窗口
            while (check(hash, T)) {
                if (min > (fast - slow + 1)) {
                    min = fast - slow + 1;
                    left = slow;
                    right = fast;
                }
                //窗口进行缩减
                hash[S.charAt(slow)]--;
                slow++;
            }
        }
        //没有找到情况
        if (left == -1 && right == -1) {
            return "";
        }
        //返回指定的字符串
        return S.substring(left, right + 1);
    }
    
    //check检查当前hash是否已经存在
    public boolean check(int[] hash, String T) {
        for (int i = 0; i < T.length(); i++) {
            if (hash[T.charAt(i)] < 0){
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

上面代码在leetcode中超时，对其进行优化：主要是针对check()函数遍历做优化，更改为一个all的int型进行表示是否已经全部包含

class Solution {
    public String minWindow(String s, String t) {
        //hash表：128个字符（ascii码）。【>=0的表示符合t中的元素，<0的即为不符合元素】
        int[] hash = new int[128];
        for (int i = 0; i < t.length(); i++) {
            hash[t.charAt(i)]++;
        }
        //保存一个最小窗口值
        int min = s.length() + 1;
        //左右指针，用于最后进行返回
        int left = -1, right = -1;
        //当前符合条件的数量
        int all = t.length();
        //滑动窗口
        for (int slow = 0, fast = 0; fast < s.length(); fast++) {
            hash[s.charAt(fast)]--;
            //说明上面对某个字符操作，该字符是属于t中的
            if (hash[s.charAt(fast)] >= 0) {
                all--;
            }
            //若是all=0表示，已经找到了所在的范围
            if (all == 0) {
                while (hash[s.charAt(slow)] < 0) {
                    hash[s.charAt(slow++)]++;
                }
                //当前范围包含t的所有元素
                if (min > (fast - slow + 1)) {
                    min = fast - slow + 1;
                    left = slow;
                    right = fast;
                }
                //此时最左边的一定是在t中包含的，此时value值+1，以及all也进行+1
                hash[s.charAt(slow++)]++;
                all++;
            }
        }
        //没有符合条件的情况
        if (min == s.length() + 1) {
            return "";
        }
        //【left,right】
        return s.substring(left, right + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

leetcode

合并区间【中等】(等同于牛客7)

题目链接：合并区间

题目内容：给出一组区间，请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。

思路：排序比较。①根据start来进行排序。②不断的进行判断star<=新添加集合中元素的end，就可以直接添加进去。

复杂度分析：

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0 || intervals.length == 1) {
            return intervals;
        }
        //1、进行排序
        Arrays.sort(intervals, (a, b)->a[0] - b[0]);
        //2、来进行排序
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= res.get(res.size() - 1)[1]) {
                res.get(res.size() - 1)[1] = Math.max(intervals[i][1], res.get(res.size() - 1)[1]);
            }else {
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[0][]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

11. 盛最多水的容器【中等】

学习：leetcode题解

题目链接：11. 盛最多水的容器

题目内容：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

思路：

1、暴力

思路：通过暴力列举出所有面积的可能性再一一比对最终求得最大面积。

复杂度分析：时间复杂度O(n²)、空间复杂度O(1)

特征：实际是两个指针同时从左边出发来进行不对列举比较，每次按照指定的顺序同步移动导致每次需要计算面积，就会有额外许多不必要的计算。

/**
 * 解法1：暴力解法
 * @param height
 * @return
 */
public int maxArea(int[] height) {
    int maxArea = 0;
    for (int i = 0; i < height.length; i++) {
        for (int j = i + 1; j < height.length; j++) {
            //最大面积 vs 当前面积（高度最矮 * 两边距离）
            maxArea = Math.max(maxArea, Math.min(height[i],height[j]) * (j - i));
        }
    }
    return maxArea;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2、左右指针

特征：左右两边
模式识别：需要移动左右两头的问题可以考虑双指针
难点：如何移动指针？①相同情况下两边距离越远越好。②区域受限于短边。
1
2
3

思路：通过不断的移动左右指针位置来减少不必要的面积计算比较，移动的依据是根据当前指针指向的两个高度比较，较矮的一方进行移动，最终来减少不必要的比较！

复杂度分析：时间复杂度O(n)、空间复杂度O(1)

/**
 * 解法2：左右指针根据两个高度大小来移动
 * @param height
 * @return
 */
public int maxArea(int[] height) {
    int max = 0, l = 0, r = height.length - 1;
    while (l < r){
        max = max = Math.max(max, Math.min(height[l],height[r]) * (r - l));
        if (height[l] < height[r]){
            l++;
        }else {
            r--;
        }
    }
    return max;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17