# 双指针技巧秒杀七道数组题目

Info

**已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~**

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

Prerequisites

Before reading this article, you should learn:

Tip

本文有视频版：Summary of Array Two-Pointer Techniques。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

When dealing with array and linked list problems, the two-pointer technique is commonly used. This technique mainly falls into two categories: **left-right pointers** and **fast-slow pointers**.

Left-right pointers are two pointers moving towards each other or away from each other; fast-slow pointers are two pointers moving in the same direction, one faster than the other.

For single linked lists, most techniques belong to the fast-slow pointer category, as covered in Six Techniques for Solving Single Linked List Problems. For example, detecting a cycle in a linked list or finding the K-th last node in a linked list are problems solved by using a `fast`

pointer and a `slow`

pointer together.

In arrays, there are no actual pointers, but we can treat indices as pointers in the array, allowing us to apply the two-pointer technique. **This article mainly discusses array-related two-pointer algorithms**.

## I. Fast-Slow Pointer Technique

### In-Place Modification

**A common fast-slow pointer technique in array problems is to modify the array in place**.

For example, consider LeetCode problem #26, "Remove Duplicates from Sorted Array," which asks you to remove duplicates from a sorted array:

**26. Remove Duplicates from Sorted Array** | 力扣 | LeetCode |

Given an integer array `nums`

sorted in **non-decreasing order**, remove the duplicates **in-place** such that each unique element appears only **once**. The **relative order** of the elements should be kept the **same**. Then return *the number of unique elements in *`nums`

.

Consider the number of unique elements of `nums`

to be `k`

, to get accepted, you need to do the following things:

- Change the array
`nums`

such that the first`k`

elements of`nums`

contain the unique elements in the order they were present in`nums`

initially. The remaining elements of`nums`

are not important as well as the size of`nums`

. - Return
`k`

.

**Custom Judge:**

The judge will test your solution with the following code:

int[] nums = [...]; // Input array int[] expectedNums = [...]; // The expected answer with correct length int k = removeDuplicates(nums); // Calls your implementation assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }

If all assertions pass, then your solution will be **accepted**.

**Example 1:**

Input:nums = [1,1,2]Output:2, nums = [1,2,_]Explanation:Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

**Example 2:**

Input:nums = [0,0,1,1,1,2,2,3,3,4]Output:5, nums = [0,1,2,3,4,_,_,_,_,_]Explanation:Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

**Constraints:**

`1 <= nums.length <= 3 * 10`

^{4}`-100 <= nums[i] <= 100`

`nums`

is sorted in**non-decreasing**order.

The function signature is as follows:

`int removeDuplicates(int[] nums);`

`int removeDuplicates(vector<int>& nums);`

`def removeDuplicates(nums: List[int]) -> int:`

`func removeDuplicates(nums []int) int {}`

`var removeDuplicates = function(nums) {};`

Let's briefly explain what in-place modification means:

If it weren't for in-place modification, we could simply create a new `int[]`

array, put the unique elements into this new array, and then return it.

However, the problem requires you to delete elements in-place, which means you cannot create a new array. You can only operate on the original array and return a length. This way, you can determine the unique elements by using the returned length and the original array.

Since the array is already sorted, duplicate elements must be adjacent, making them easy to find. But if you delete each duplicate element immediately, the time complexity can reach `O(N^2)`

due to the data movement involved in deleting elements from an array.

To solve this problem efficiently, we use the two-pointer technique:

We let the slow pointer `slow`

follow behind, while the fast pointer `fast`

explores ahead. When `fast`

finds a non-duplicate element, it assigns it to `slow`

and moves `slow`

one step forward.

This ensures that `nums[0..slow]`

contains only unique elements. When the `fast`

pointer has traversed the entire array `nums`

, `nums[0..slow]`

will be the result of the array with duplicates removed.

Here's the code:

```
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// maintain nums[0..slow] with no duplicates
nums[slow] = nums[fast];
}
fast++;
}
// the length of the array is index + 1
return slow + 1;
}
}
```

```
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.size()) {
if (nums[fast] != nums[slow]) {
slow++;
// maintain no duplicates in nums[0..slow]
nums[slow] = nums[fast];
}
fast++;
}
// the length of the array is index + 1
return slow + 1;
}
};
```

```
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
slow = 0
fast = 1
while fast < len(nums):
if nums[fast] != nums[slow]:
slow += 1
# maintain nums[0..slow] without duplicates
nums[slow] = nums[fast]
fast += 1
# the length of the array is index + 1
return slow + 1
```

```
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
slow,fast :=0,0
for fast<len(nums) {
if nums[fast] != nums[slow] {
slow++
// maintain nums[0..slow] with no duplicates
nums[slow] = nums[fast]
}
fast++
}
// the length of the array is index + 1
return slow + 1
}
```

```
var removeDuplicates = function(nums) {
if (nums.length == 0) {
return 0;
}
var slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// maintain nums[0..slow] with no duplicates
nums[slow] = nums[fast];
}
fast++;
}
// the length of the array is index + 1
return slow + 1;
};
```

You can refer to the visualization panel to understand the process of algorithm execution:

Let's briefly expand on this. Take a look at LeetCode problem #83, "Remove Duplicates from Sorted List." If you are given a sorted singly linked list, how would you remove the duplicates?

In fact, it is exactly the same as removing duplicates from an array. The only difference is that you change the array assignment operations to pointer operations. Compare it with the previous code:

```
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// disconnect from the following duplicate elements
slow.next = null;
return head;
}
}
```

```
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr) return nullptr;
ListNode* slow = head, *fast = head;
while (fast != nullptr) {
if (fast->val != slow->val) {
// nums[slow] = nums[fast];
slow->next = fast;
// slow++;
slow = slow->next;
}
// fast++
fast = fast->next;
}
// disconnect from the following duplicate elements
slow->next = nullptr;
return head;
}
};
```

```
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None:
return None
slow, fast = head, head
while fast is not None:
if fast.val != slow.val:
# nums[slow] = nums[fast];
slow.next = fast
# slow++;
slow = slow.next
# fast++
fast = fast.next
# disconnect from the following duplicate elements
slow.next = None
return head
```

```
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return nil
}
slow, fast := head, head
for fast != nil {
if fast.Val != slow.Val {
// nums[slow] = nums[fast];
slow.Next = fast
// slow++;
slow = slow.Next
}
// fast++
fast = fast.Next
}
// disconnect from the following duplicate elements
slow.Next = nil
return head
}
```

```
var deleteDuplicates = function(head) {
if (head === null) return null;
let slow = head, fast = head;
while (fast !== null) {
if (fast.val !== slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// disconnect from the following duplicate elements
slow.next = null;
return head;
};
```

To see the process of the algorithm execution, please refer to the following visualization panel:

注

Some readers might wonder, "The duplicate elements in the linked list aren't actually removed; they're just left hanging there. Is that appropriate?"

This brings us to the discussion of different language features. Languages like Java and Python, which have garbage collection, can automatically find and reclaim the memory of these "dangling" linked list nodes. However, languages like C++, which lack automatic garbage collection, require us to manually release the memory of these nodes when writing code.

That said, in terms of cultivating algorithmic thinking, it's sufficient to understand this fast-slow pointer technique.

**Besides asking you to remove duplicates from sorted arrays/lists, problems might also require you to "remove" certain elements from an array in place**.

For example, LeetCode problem #27 "Remove Element". Here's the problem statement:

**27. Remove Element** | 力扣 | LeetCode |

Given an integer array `nums`

and an integer `val`

, remove all occurrences of `val`

in `nums`

**in-place**. The order of the elements may be changed. Then return *the number of elements in *`nums`

* which are not equal to *`val`

.

Consider the number of elements in `nums`

which are not equal to `val`

be `k`

, to get accepted, you need to do the following things:

- Change the array
`nums`

such that the first`k`

elements of`nums`

contain the elements which are not equal to`val`

. The remaining elements of`nums`

are not important as well as the size of`nums`

. - Return
`k`

.

**Custom Judge:**

The judge will test your solution with the following code:

int[] nums = [...]; // Input array int val = ...; // Value to remove int[] expectedNums = [...]; // The expected answer with correct length. // It is sorted with no values equaling val. int k = removeElement(nums, val); // Calls your implementation assert k == expectedNums.length; sort(nums, 0, k); // Sort the first k elements of nums for (int i = 0; i < actualLength; i++) { assert nums[i] == expectedNums[i]; }

If all assertions pass, then your solution will be **accepted**.

**Example 1:**

Input:nums = [3,2,2,3], val = 3Output:2, nums = [2,2,_,_]Explanation:Your function should return k = 2, with the first two elements of nums being 2. It does not matter what you leave beyond the returned k (hence they are underscores).

**Example 2:**

Input:nums = [0,1,2,2,3,0,4,2], val = 2Output:5, nums = [0,1,4,0,3,_,_,_]Explanation:Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4. Note that the five elements can be returned in any order. It does not matter what you leave beyond the returned k (hence they are underscores).

**Constraints:**

`0 <= nums.length <= 100`

`0 <= nums[i] <= 50`

`0 <= val <= 100`

```
// The function signature is as follows
int removeElement(int[] nums, int val);
```

```
// The function signature is as follows
int removeElement(vector<int>& nums, int val);
```

```
# The function signature is as follows
def removeElement(nums: List[int], val: int) -> int:
```

```
// The function signature is as follows
func removeElement(nums []int, val int) int {}
```

```
// The function signature is as follows
var removeElement = function(nums, val) {};
```

The problem requires us to remove all elements with the value `val`

from the array `nums`

in place, using the fast and slow pointer technique:

If `fast`

encounters an element with the value `val`

, it skips it. Otherwise, it assigns the value to the `slow`

pointer and moves the `slow`

pointer forward.

This approach is exactly the same as the solution for the array deduplication problem mentioned earlier. Let's directly look at the code:

```
class Solution {
public int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
```

```
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.size()) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
```

```
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
fast, slow = 0, 0
while fast < len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
```

```
func removeElement(nums []int, val int) int {
fast, slow := 0, 0
for fast < len(nums) {
if nums[fast] != val {
nums[slow] = nums[fast]
slow++
}
fast++
}
return slow
}
```

```
var removeElement = function(nums, val) {
var fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
```

You can refer to the visualization panel to understand the process of the algorithm execution:

Note that there is a subtle difference from the solution for removing duplicates from a sorted array. Here, we assign `nums[slow]`

first and then increment `slow`

. This ensures that the elements in `nums[0..slow-1]`

do not contain the value `val`

. The length of the resulting array is `slow`

.

After implementing the `removeElement`

function, let's look at LeetCode problem #283, "Move Zeroes":

Given an array `nums`

, modify it **in place** to move all elements with the value 0 to the end of the array. The function signature is as follows:

`void moveZeroes(int[] nums);`

`void moveZeroes(vector<int>& nums);`

`def moveZeroes(nums: List[int]) -> None:`

`func moveZeroes(nums []int) {}`

`function moveZeroes(nums) {}`

For example, if you are given the input `nums = [0,1,4,0,2]`

, your algorithm does not return a value, but it will modify the `nums`

array in place to become `[1,4,2,0,0]`

.

Considering the previous questions, do you already have an answer in mind?

You can solve this problem by slightly modifying the `removeElement`

function from the last question, or you can even reuse the `removeElement`

function directly.

The problem asks us to move all zeros to the end, which is essentially the same as removing all zeros from `nums`

and then setting the remaining elements to zero:

```
class Solution {
public void moveZeroes(int[] nums) {
// remove all 0s from nums, return the length of the array without 0s
int p = removeElement(nums, 0);
// assign elements of nums[p..] to 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
public int removeElement(int[] nums, int val) {
// see the above code implementation
}
}
```

```
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// remove all 0s from nums, return the length of the array without 0s
int p = removeElement(nums, 0);
// assign elements of nums[p..] to 0
for (; p < nums.size(); p++) {
nums[p] = 0;
}
}
int removeElement(vector<int>& nums, int val) {
// see the previous code implementation
}
};
```

```
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
# remove all 0 from nums and return the length of the array without 0
p = self.removeElement(nums, 0)
# assign elements of nums[p..] to 0
for i in range(p, len(nums)):
nums[i] = 0
def removeElement(self, nums: List[int], val: int) -> int:
# see the above code implementation
```

```
func moveZeroes(nums []int) {
// remove all 0s from nums and return the length of the array without 0s
p := removeElement(nums, 0)
// assign elements of nums[p..] to 0
for ; p < len(nums); p++ {
nums[p] = 0
}
}
func removeElement(nums []int, val int) int {
// see the implementation in the above code
}
```

```
var moveZeroes = function(nums) {
// remove all 0s from nums and return the length of the array without 0s
var p = removeElement(nums, 0);
// assign elements of nums[p..] to 0
for (let i = p; i < nums.length; i++) {
nums[i] = 0;
}
};
var removeElement = function(nums, val) {
// see the above code implementation
};
```

At this point, we've covered most of the problems involving in-place modification of arrays.

### Sliding Window

Another major category of fast-slow pointer problems in arrays is the "Sliding Window Algorithm." In another article, Detailed Explanation of the Sliding Window Algorithm Core Framework, I provide the code framework for the sliding window:

```
// Pseudocode for the sliding window algorithm framework
int left = 0, right = 0;
while (right < nums.size()) {
// Expand the window
window.addLast(nums[right]);
right++;
while (window needs shrink) {
// Shrink the window
window.removeFirst(nums[left]);
left++;
}
}
```

This article won't repeat specific problems. Instead, it emphasizes the fast and slow pointer characteristics of the sliding window algorithm:

The `left`

pointer follows behind, while the `right`

pointer leads ahead. The section between these two pointers forms the "window." The algorithm solves certain problems by expanding and contracting this "window."

## II. Common Algorithms Using Left and Right Pointers

### Binary Search

In another article Binary Search Framework Explained, I discuss the details of binary search code in depth. Here, I'll only present the simplest binary search algorithm to highlight its dual-pointer characteristics:

```
int binarySearch(int[] nums, int target) {
// two pointers, one on the left and one on the right, move towards each other
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = (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;
}
```

```
#include <vector>
using namespace std;
int binarySearch(vector<int>& nums, int target) {
// two pointers, one on the left and one on the right, move towards each other
int left = 0, right = nums.size() - 1;
while(left <= right) {
int mid = (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;
}
```

```
def binarySearch(nums: List[int], target: int) -> int:
# two pointers, one on the left and one on the right, move towards each other
left, right = 0, len(nums) - 1
while left <= right:
mid = (right + left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
```

```
func binarySearch(nums []int, target int) int {
// two pointers, one on the left and one on the right, moving towards each other
left, right := 0, len(nums)-1
for left <= right {
mid := (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
}
```

```
var binarySearch = function(nums, target) {
// two pointers, one on the left and one on the right, moving towards each other
var left = 0;
var right = nums.length - 1;
while(left <= right) {
var mid = Math.floor((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;
}
```

### Sum of `n`

Numbers

Take a look at LeetCode problem 167, "Two Sum II":

**167. Two Sum II - Input Array Is Sorted** | 力扣 | LeetCode |

Given a **1-indexed** array of integers `numbers`

that is already ** sorted in non-decreasing order**, find two numbers such that they add up to a specific

`target`

number. Let these two numbers be `numbers[index`_{1}]

and `numbers[index`_{2}]

where `1 <= index`_{1} < index_{2} <= numbers.length

.Return* the indices of the two numbers, *`index`

_{1}* and *`index`

_{2}*, added by one as an integer array *

`[index`_{1}, index_{2}]

*of length 2.*

The tests are generated such that there is **exactly one solution**. You **may not** use the same element twice.

Your solution must use only constant extra space.

**Example 1:**

Input:numbers = [2,7,11,15], target = 9Output:[1,2]Explanation:The sum of 2 and 7 is 9. Therefore, index_{1}= 1, index_{2}= 2. We return [1, 2].

**Example 2:**

Input:numbers = [2,3,4], target = 6Output:[1,3]Explanation:The sum of 2 and 4 is 6. Therefore index_{1}= 1, index_{2}= 3. We return [1, 3].

**Example 3:**

Input:numbers = [-1,0], target = -1Output:[1,2]Explanation:The sum of -1 and 0 is -1. Therefore index_{1}= 1, index_{2}= 2. We return [1, 2].

**Constraints:**

`2 <= numbers.length <= 3 * 10`

^{4}`-1000 <= numbers[i] <= 1000`

`numbers`

is sorted in**non-decreasing order**.`-1000 <= target <= 1000`

- The tests are generated such that there is
**exactly one solution**.

Whenever you have a sorted array, you should think of the two-pointer technique. The solution to this problem is somewhat similar to binary search. By adjusting `left`

and `right`

, you can control the value of `sum`

:

```
class Solution {
public int[] twoSum(int[] numbers, int target) {
// one left and one right pointers moving towards each other
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
// the index required by the problem starts from 1
return new int[]{left + 1, right + 1};
} else if (sum < target) {
// make the sum a little bigger
left++;
} else if (sum > target) {
// make the sum a little smaller
right--;
}
}
return new int[]{-1, -1};
}
}
```

```
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
// one pointer on the left and one on the right moving towards each other
int left = 0, right = numbers.size() - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
// the indices required by the problem start from 1
return vector<int>{left + 1, right + 1};
} else if (sum < target) {
// make the sum a bit larger
left++;
} else if (sum > target) {
// make the sum a bit smaller
right--;
}
}
return vector<int>{-1, -1};
}
};
```

```
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
# one pointer on the left and one on the right moving towards each other
left, right = 0, len(numbers) - 1
while left < right:
sum = numbers[left] + numbers[right]
if sum == target:
# the index required by the problem starts from 1
return [left + 1, right + 1]
elif sum < target:
# make the sum a little bigger
left += 1
elif sum > target:
# make the sum a little smaller
right -= 1
return [-1, -1]
```

```
func twoSum(nums []int, target int) []int {
// two pointers, one on the left and one on the right, move towards each other
left, right := 0, len(nums) - 1
for left < right {
sum := nums[left] + nums[right]
if sum == target {
// the index required by the problem starts from 1
return []int{left + 1, right + 1}
} else if sum < target {
// make the sum a little bigger
left++
} else if sum > target {
// make the sum a little smaller
right--
}
}
return []int{-1, -1}
}
```

```
var twoSum = function(nums, target) {
// two pointers, one on the left and one on the right, move towards each other
var left = 0, right = nums.length - 1;
while (left < right) {
var sum = nums[left] + nums[right];
if (sum == target) {
// the index required by the problem starts from 1
return [left + 1, right + 1];
} else if (sum < target) {
// make the sum a bit larger
left++;
} else if (sum > target) {
// make the sum a bit smaller
right--;
}
}
return [-1, -1];
}
```

In another article One Function to Solve All nSum Problems, I also used a similar left-right pointer technique to provide a general approach to the `nSum`

problem, which essentially leverages the two-pointer technique.

### Reverse Array

Most programming languages provide a `reverse`

function. The principle behind this function is actually very simple. LeetCode problem 344 "Reverse String" is a similar requirement, asking you to reverse a `char[]`

type character array. Let's directly look at the code:

```
void reverseString(char[] s) {
// two pointers, one on the left and one on the right, moving towards each other
int left = 0, right = s.length - 1;
while (left < right) {
// swap s[left] and s[right]
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
```

```
void reverseString(vector<char>& s) {
// two pointers, one on the left and one on the right, move towards each other
int left = 0, right = s.size() - 1;
while (left < right) {
// swap s[left] and s[right]
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
```

```
def reverseString(s: List[str]) -> None:
# two pointers, one on the left and one on the right, move towards each other
left, right = 0, len(s) - 1
while left < right:
# swap s[left] and s[right]
temp = s[left]
s[left] = s[right]
s[right] = temp
left += 1
right -= 1
```

```
func reverseString(s []rune) {
// two pointers, one on the left and one on the right, move towards each other
left, right := 0, len(s)-1
for left < right {
// swap s[left] and s[right]
temp := s[left]
s[left] = s[right]
s[right] = temp
left++
right--
}
}
```

```
var reverseString = function(s) {
// two pointers, one on the left and one on the right, move towards each other
var left = 0, right = s.length - 1;
while (left < right) {
// swap s[left] and s[right]
var temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
```

For more advanced problems related to array reversal, you can refer to Creative Traversals of 2D Arrays.

### Palindrome Check

A palindrome is a string that reads the same forwards and backwards. For example, the strings `aba`

and `abba`

are palindromes because they are symmetrical and remain the same when reversed. Conversely, the string `abac`

is not a palindrome.

You might now realize that palindrome problems are closely related to the concept of left and right pointers. For instance, if you need to determine whether a string is a palindrome, you can write the following code:

```
boolean isPalindrome(String s) {
// two pointers, one on the left and one on the right, move towards each other
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
```

```
bool isPalindrome(string s) {
// two pointers, one on the left and one on the right, move towards each other
int left = 0, right = s.length() - 1;
while (left < right) {
if (s[left] != s[right]) {
return false;
}
left++;
right--;
}
return true;
}
```

```
def isPalindrome(s: str) -> bool:
# two pointers, one on the left and one on the right, moving towards each other
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
```

```
func isPalindrome(s string) bool {
// two pointers, one on the left and one on the right, move towards each other
left, right := 0, len(s) - 1
for left < right {
if s[left] != s[right] {
return false
}
left++
right--
}
return true
}
```

```
var isPalindrome = function(s) {
// two pointers, one on the left and one on the right, move towards each other
var left = 0, right = s.length - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
```

Next, let's increase the difficulty a bit. Given a string, can you use the two-pointer technique to find the longest palindrome substring within it?

This is LeetCode problem #5, "Longest Palindromic Substring":

**5. Longest Palindromic Substring** | 力扣 | LeetCode |

Given a string `s`

, return *the longest* *palindromic* *substring* in `s`

.

**Example 1:**

Input:s = "babad"Output:"bab"Explanation:"aba" is also a valid answer.

**Example 2:**

Input:s = "cbbd"Output:"bb"

**Constraints:**

`1 <= s.length <= 1000`

`s`

consist of only digits and English letters.

The function signature is as follows:

`String longestPalindrome(String s);`

`string longestPalindrome(string s);`

`def longestPalindrome(s: str):`

`func longestPalindrome(s string) string {}`

```
var longestPalindrome = function(s) {
};
```

The challenge in finding palindromic substrings lies in the fact that the length of a palindrome can be either odd or even. The key to solving this problem is the **two-pointer technique that expands from the center to both ends**.

If the length of the palindrome is odd, it has a single center character; if the length is even, it can be considered to have two center characters. Therefore, we can start by implementing a function like this:

```
// Find the longest palindrome centered with s[l] and s[r] in s
String palindrome(String s, int l, int r) {
// prevent index out of bounds
while (l >= 0 && r < s.length()
&& s.charAt(l) == s.charAt(r)) {
// two pointers, expand to both sides
l--; r++;
}
// return the longest palindrome centered with s[l] and s[r]
return s.substring(l + 1, r);
}
```

```
// Find the longest palindrome centered with s[l] and s[r] in s
std::string palindrome(std::string s, int l, int r) {
// Prevent index out of bounds
while (l >= 0 && r < s.length()
&& s[l] == s[r]) {
// Two pointers expand to both sides
l--; r++;
}
// Return the longest palindrome centered with s[l] and s[r]
return s.substr(l + 1, r-l-1);
}
```

```
# Find the longest palindrome in s with s[l] and s[r] as the center
def palindrome(s: str, l: int, r: int) -> str:
# Prevent index out of bounds
while l >= 0 and r < len(s) and s[l] == s[r]:
# Two pointers, expand to both sides
l -= 1
r += 1
# Return the longest palindrome with s[l] and s[r] as the center
return s[l + 1: r]
```

```
// Find the longest palindrome in s with s[l] and s[r] as the center
func palindrome(s string, l int, r int) string {
// Prevent index out of bounds
for l >= 0 && r < len(s) && s[l] == s[r] {
// Two pointers, expand to both sides
l--
r++
}
// Return the longest palindrome with s[l] and s[r] as the center
return s[l+1 : r]
}
```

```
var palindrome = function(s, l, r) {
// find the longest palindrome in s with s[l] and s[r] as the center
// prevent index out of bounds
while (l >= 0 && r < s.length
&& s.charAt(l) == s.charAt(r)) {
// two pointers, expand to both sides
l--; r++;
}
// return the longest palindrome with s[l] and s[r] as the center
return s.substring(l + 1, r);
}
```

This way, if you input the same `l`

and `r`

, it means you are looking for a palindrome of odd length. If you input adjacent `l`

and `r`

, it means you are looking for a palindrome of even length.

Now, coming back to the problem of finding the longest palindrome, the general approach is:

```
for 0 <= i < len(s):
Find the palindrome centered at s[i]
Find the palindrome centered at s[i] and s[i+1]
Update the answer
```

Translating this into code can solve the problem of finding the longest palindromic substring:

```
String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// the longest palindrome substring with s[i] as the center
String s1 = palindrome(s, i, i);
// the longest palindrome substring with s[i] and s[i+1] as the centers
String s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
```

```
string longestPalindrome(string s) {
string res = "";
for (int i = 0; i < s.length(); i++) {
// the longest palindromic substring centered at s[i]
string s1 = palindrome(s, i, i);
// the longest palindromic substring centered at s[i] and s[i+1]
string s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
```

```
def longestPalindrome(s: str) -> str:
res = ""
for i in range(0, len(s)):
# the longest palindrome substring centered at s[i]
s1 = palindrome(s, i, i)
# the longest palindrome substring centered at s[i] and s[i+1]
s2 = palindrome(s, i, i + 1)
# res = longest(res, s1, s2)
res = s1 if len(res) < len(s1) else res
res = s2 if len(res) < len(s2) else res
return res
```

```
func longestPalindrome(s string) string {
var res string
for i := 0; i < len(s); i++ {
// the longest palindromic substring centered at s[i]
s1 := palindrome(s, i, i)
// the longest palindromic substring centered at s[i] and s[i+1]
s2 := palindrome(s, i, i+1)
// res = longest(res, s1, s2)
if len(res) < len(s1) {
res = s1
}
if len(res) < len(s2) {
res = s2
}
}
return res
}
```

```
var longestPalindrome = function(s) {
var res = "";
for (var i = 0; i < s.length; i++) {
// the longest palindrome substring centered at s[i]
var s1 = palindrome(s, i, i);
// the longest palindrome substring centered at s[i] and s[i+1]
var s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length > s1.length ? res : s1;
res = res.length > s2.length ? res : s2;
}
return res;
}
```

You might notice that the left and right pointers used in finding the longest palindromic substring differ from those in previous problems: in previous problems, the pointers move towards each other from both ends, whereas in the palindromic substring problem, the pointers expand outwards from the center. However, this situation is specific to palindrome problems, so I still categorize it under left and right pointers.

With this, we have covered all the two-pointer techniques related to arrays. For more extensions and practice problems, see More Classic and Frequent Array Two-Pointer Problems.

**引用本文的题目**

**安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：**