在我们练习Java算法的时候,难免会遇到一些题目利用一些技巧性的解题方法比不用要强很多,这次主要分享一下有关双针的技巧。
双指针一般分为两类:一类是快慢指针,一类是左右指针。前者解决主要链表中的问题,比如典型的判断链表中是否包含环;后者主要解决数组(或字符串)中的问题,比如二分查找。
链表中要想不含环,那么这个指针最终会遇到空指针 null
表示链表到头了,这还好说,可以判断该链表不含环
boolean hasCycle(ListNode head) { while (head != null) { head = head.next; } return false; }
如果链表中存在环了,那么上述的代码就会陷入死循环,因为环形数组中没有 null
指针作为尾部节点。
经典解法就是用两个指针,一个跑的快,一个跑的慢,如果不含有环,跑的快的那个指针最终会遇到 null
,说明链表不含有环。如果快指针最终会超满指针一圈,和慢指针相遇,说明链表含有环。
boolean hasCycle(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; // 如果两个指针相遇,说明构成了环,返回 true if (fast = slow) { return true; } } return false; }
ListNode detectCycle(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow = fast) { break; } } if (fast == null || fast.next == null) { // fast 没有遇到环,遇到了空指针 return null; } slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; }
当快慢指针相遇的时候,让其中一个指针指向头节点,然后再让快慢指针以相同的速度前进,再次相遇的时候,就是环开始的位置。
解释:
第一次相遇时,假设慢指针 slow
走了 k
步,那么快指针 fast
一定走了 2k 步;
fast
一定比 slow
多走了 k
步,这多走的 k
步其实就是 fast
指针在环里转圈圈,所以 k
的值就是环长度的整数倍。
假设相遇点距离环的起点的距离为 m
,那么环的起点距头节点 head
的距离就是 k - m
,也就是说如果从 head
前进 k - m
步就能到达环起点。
巧的是,如果从相遇点继续前进 k - m
步,也恰好到达环起点,甭管 fast
在环里转了几圈,走 k
步到相遇点,那走 k - m
步一定就是走到环起点了
所以,只要我们把快慢指针中的任一重新指向 head
,然后两个指针同速前进,k - m
步就会相遇,相遇之处就是环的起点了。
左右指针在数组中实际上是指两个索引值,一般初始化为 left = 0, right = nums.length - 1
int binarySearch(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = (right + left) / 2; if (nums[mid] == target) { return mid; } if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } } return - 1; }
只要数组有序,我们就应该想到双指针的技巧,
int[] twoSum(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { return new int[]{left, right} } else if (sum < target) { // 让 sum 大一些 left++; } else if (sum > target) { // 让 sum 小一些 right--; } } return new int[]{-1, -1}; }
反转一个 char[]
类型的字符串数组
void reverseString(char[] arr) { int left = 0, right = arr.length - 1; while (left <= right) { arr[left] = arr[left] + arr[right]; arr[right] = arr[left] - arr[right]; arr[left] = arr[left] - arr[right]; left++; right--; } }
如果这几个例子可以掌握了,那么双指针基本的思想,以及链表等基本操作也就可以掌握了,掌握了基本的技巧,还需要经过做一些题目进行打磨,多写一些题目会更加深刻的理解。