双指针技巧

双指针有两类:

  • 快慢指针
    • 一般用于解决链表相关的问题,如判断链表是否存在环
  • 左右指针
    • 一般用于解决数组相关的问题,如二分查找

快慢指针


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

判断链表中是否存在环

因为单链表的特点是每个节点只知道下一个节点,所以一个指针的话无法判断链表中是否含有环的。

使用快慢指针的思想解决链表中是否存在环的问题,其实是非常简单的,快慢指针初始时都指向链表头结点,慢指针每次前进一步,快指针每次前进两步。

  • 如果链表不存在环,那么快指针最终会运行到链表的终端节点
  • 如果链表存在环,那么快指针会多跑一会然后追上慢指针,此时说明链表存在环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;

while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;

if (fast == slow) {
return true;
}
}
return false;
}

已知链表中存在环,返回环的的起始位置

<
br />

关于计算环的起点这个,需要用到一点的数学知识,我们假定快慢指针在4这个位置相遇了。同时我们做如下约定:

  • 表头1到环起点3之间的距离我们记录为m
  • 节点3和节点4之间的距离我们记录为n
  • 环的长度我们记录为r
  • slow指针从表头1到当前位置4一共经过的距离我们记录为k

因此我们会有如下结论:

  • slow指针走的距离为k, 我们很容易得出k=m+n,那么fast指针走的距离就会是2k, 假定相遇时fast走了p圈,所以fast指针走的距离为:m + pr + n
  • 根据上一步的推理,我们会有如下的等式:pr + n + m = 2k = 2m + 2n
  • 所以pr = m + n. 所以我们可以得出,节点4顺时针到节点3的距离为 pr - n = m。其实可以推断出p = 1的。所以节点4顺时针到节点3的距离和节点1到节点3的距离是相等的。因此我们的算法代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
boolean getCycleStartPosition(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;

//第一次相遇推出循环
if (fast == slow) {
break;
}
}

//将慢指针设置为起点,然后快慢指针都每次走一步
slow = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}

寻找链表中间节点


这个问题的解法思路也是用快慢指针,期初2个指针都指向链表头部,然后慢指针每次走一步,快指针每次走两步,当快指针到达链表结尾时,慢指针的位置就是链表的中间节点。

1
2
3
4
5
6
7
8
9
10

ListNode getMidNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}

当链表的长度是奇数时,slow 恰巧停在中点位置;如果长度是偶数,slow 最终的位置是中间偏右

寻找链表的倒数第 k 个元素

这个问题换是快慢指针的事情,这次快慢指针都是每次走一步,但是得先让快指针提前走k步而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode getLastKNode(ListNode head, int k) {
if (head == null || k < 0) {
return null;
}
ListNode fast = head;
ListNode slow = head;

for(int i = 0; i < k; i++) {
fast = fast.next;
if (fast == null) {
return null;
}
}

while(fast != null && fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}

二分查找一般解法

二分查找模板

二分查找一般容易犯错的地方有3个:

  • 应该给mid加1还是应该减1,还是不加不减
  • 上层的while循环里面的条件应该是left < right还是 left <= right
  • 计算mid时,最好是采用mid = left + (right - left)/2而不是mid = (left + right) /2。因为这样可以避免int溢出。


二分查找的一般框架为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length ...;

while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
...
} else if (nums[mid] > target) {
...
}
}
return ...
}

上面框架中省略的地方,其实就是比较容易出问题的地方。


下面直接给出二分查找的算法模板,一般只需要熟记其中之一就好了。我一般都采样第一个:


总结一下2个模板的记忆方法:

  • 如果初始化right = nums.length -1, 那么使用left <= right,并且right = mid - 1
  • 如果初始化right = nums.length那么使用left < right, 并且right = mid

    模板1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1; //注意

    while( left <= right ) { //注意
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
    //找到目标值的相关逻辑
    return mid;
    } else if (nums[mid] < target) {
    left = mid + 1; //注意
    } else if (nums[mid] > target) {
    right = mid - 1; //注意
    }
    }
    //没找到目标值的相关逻辑
    return -1;
    }

    模板2

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length; //注意

    while( left < right ) { //注意
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
    //找到目标值的相关逻辑
    return mid;
    } else if (nums[mid] < target) {
    left = mid + 1;
    } else if (nums[mid] > target) {
    right = mid //注意
    }
    }
    //没找到目标值的相关逻辑
    return -1;
    }


下面通过一些例子来使用一下模板

寻找一个数

这个场景是最简单的,肯能也是大家最熟悉的,即在递增序列中搜索一个数,如果存在,返回其索引,否则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; //注意

while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; //注意
} else if (nums[mid] > target) {
right = mid - 1; //注意
}
}
return -1;
}

LeetCode上面有一个题目,[374. 猜数字大小] 其实就是最简单和标准的二分查找算法。

二分查找的变种问题

查找左右边界


这类题目一般的特点为:

  • 数组有序,但是有重复元素
  • 数组部分有序,不包含重复元素
  • 数组部分有序,包含重复元素。

查找左边界


既然要寻找左边界,搜索范围就需要从右边开始,不断往左边收缩,也就是说即使我们找到了nums[mid] == target, 这个mid的位置也不一定就是最左侧的那个边界,我们还是要向左侧查找,所以我们在nums[mid]偏大或nums[mid]就等于目标值的时候,继续收缩右边界, 不过需要注意最终while循环外需要外检查一下边界情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 检查出界情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}

### 查找右边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 这里改成收缩左侧边界即可
left = mid + 1;
}
}
// 这里改为检查 right 越界的情况,见下图
if (right < 0 || nums[right] != target)
return -1;
return right;
}
## 参考文章:

leetcode-28 实现strStr()

题目描述:

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/implement-strstr
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

我的第一版答案:

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
class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null) return 0;
if (needle == null) return 0;
int haystackLength = haystack.length();
int needleLength = needle.length();
if (needleLength > haystackLength) {
return -1;
}

for (int i = 0; i < (haystack.length() - needleLength + 1); i++) {
int j =0;
while(j < needleLength) {
if (haystack.charAt(i + j) == needle.charAt(j)) {
j ++;
} else {
break;
}
}
if (j == needleLength) {
return i;
}
}
return -1;
}
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×