双指针算法的应用举例

求有序数组的两数之和给定一个有序整数数组和一个目标值，找出数组中和为目标值的两个数。

思路：定义两个指针，一个指向数组头部，一个指向数组尾部。根据数组有序的特点，若两个指针所指元素之和大于目标值，则右指针向左移动一位，若两数之和小于目标值，则左指针向右移动一位。直到找到两数之和等于目标值为止。

代码：

class Solution { public 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 + 1, right + 1}; } else if (sum < target) { left++; } else { right--; } } return new int[]{-1, -1}; } }

判断链表是否存在环给定一个链表，判断链表中是否有环。

思路：定义快慢两个指针，快指针每次走两步，慢指针每次走一步。若链表中存在环，则快指针最终一定会追上慢指针，否则快指针会先到达链表尾部。

代码：

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

求最长回文子串给定一个字符串，求其中最长的回文子串。

思路：定义两个指针，分别从字符串的左右两端开始向中间移动，并判断当前子串是否为回文串。如果是，则更新最长回文子串的长度和起始位置。

代码：

public String longestPalindrome(String s) { int maxLen = 0, start = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > maxLen) { maxLen = len; start = i - (len - 1) / 2; } } return s.substring(start, start + maxLen); }

private int expandAroundCenter(String s, int left, int right) { while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) { left--; right++; } return right - left - 1;