侧边栏壁纸
  • 累计撰写 416 篇文章
  • 累计创建 65 个标签
  • 累计收到 145 条评论

目 录CONTENT

文章目录

名词解释-双指针算法

Z同学
2022-10-07 / 0 评论 / 1 点赞 / 423 阅读 / 1,234 字
温馨提示:
本文最后更新于 2022-10-12,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

1. 解释

其实双指针算法,并不是一种具体的公式或者范式。而是一种思路。一种节省时间运算的思路。

通常是指通过设置两个指针不断进行单向移动来解决问题的形式。

双指针算法的核心用途就是:优化时间复杂度

而我们经常使用双指针的场景就是两层循环。

指针,其实就代表了我们循环过程中的下标值。

我们讲了,双指针只是一种思路。而针对某些场景大家使用双指针总结了一些通用范例。

  • 左右指针:创建两个指针(变量),一个指向开头,一个指向末尾,然后向中间遍历,直到满足条件或者两个指针相遇;
  • 快慢指针:常见于链表查询中。创建两个指针,开始都指向开头,根据条件不同,快指针走得快,慢指针走的慢,直到满足条件或者快指针走到结尾;
  • 滑动窗口:进行单调性的子串问题。创建两个指针,两个指针包裹的范围叫做窗口,然后通过移动指针,匹配窗口中的条件是否满足要求。

下面针对这几种范例场景,进行简单学习和了解。

2. 左右指针

通常,我们在有序数组中使用左右指针的情况较多。

例如:我们有一个数组nums,我们要找其中某个值。那么我们使用的二分查找,就是所谓的左右指针了。

public int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;//搜索区间为[left,right] ,就是两个指针了
    while (left <= right) {//设定终止条件。
        int mid = left + (right - left) / 2;//不用mid=(left+right)/2 是为了防止left+right溢出>Integer.Maxvalue就会边为负数
        if (nums[mid] < target) {
            left = mid + 1;//缩小左边界,区间[mid+1,right], 也就是指针移动
        } else if (nums[mid] > target) {
            right = mid - 1;//缩小右边界,区间[left,mid-1], 也就是指针移动
        } else {
            return mid;//搜索到目标区间,nums[mid]=target,return mid
        }
    }
    return -1; //遍历数组没有找到target
}

3. 快慢指针

比较常见的情况就是在链表中进行查询处理。例如我们要判断一串链表数据中,有没有环。

也就是某个链表的值是前面链表的值。例如下图所示:

image-1665560059690

示例代码:

public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

快慢指针一般都初始化指向链表的头结点head,前进时快指针fast在前,慢指针slow在后,巧妙解决一些链表中的问题。

上面的示例只是简单的情况,我们还可以使用快慢指针,实现查找链表中指定倒数第N个元素的值。

将快指针值,先加上指定N步。然后让快慢指针开始同速前进,当快指针走到末尾null。那么慢指针指向的就是我们的要求了。

4. 滑动窗口

这个概念的命名可以说是很直观了,通过两个指针指向的元素之间形成的一个窗口,然后我们滑动这个窗口进行数据比对。直到满足要求的数据为止。

而这个窗口分两种,一种是固定大小的窗口,一个是大小动态变化的窗口。

而应用场景和要求:

  1. 一般给出的数据结构是数组或者字符串
  2. 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
  3. 该问题本身可以通过暴力求解

例如 无重复字符的最长子串 的示例:

    public int lengthOfLongestSubstring(String s) {
        // 哈希集合,记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格,移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

就是一个典型的利用滑动窗口的思路,来实现的算法。

1

评论区