1. Overview

1.概述

In this tutorial, we’ll discuss the two-pointer approach for solving problems involving arrays and lists. This technique is an easy and efficient way to improve the performance of our algorithm.

在本教程中，我们将讨论用于解决涉及数组和列表问题的双指针方法。这种技术是提高我们算法性能的一种简单而有效的方法。。

2. Technique Description

2.技术说明

In many problems involving arrays or lists, we have to analyze each element of the array compared to its other elements.

在许多涉及数组或列表的问题中，我们必须将数组中的每个元素与其他元素相比进行分析。

To solve problems like these we usually start from the first index and loop through the array one or more times depending on our implementation. Sometimes, we also have to create a temporary array depending on our problem’s requirements.

为了解决这样的问题，我们通常从第一个索引开始，根据我们的实现，在数组中循环一次或多次。有时，我们还必须根据问题的要求，创建一个临时数组。

The above approach might give us the correct result, but it likely won’t give us the most space- and time-efficient solution.

上述方法可能会给我们带来正确的结果，但它很可能不会给我们带来最节省空间和时间的解决方案。

As a result, it is often good to consider whether our problem can be solved efficiently by using the two-pointers approach.

因此，考虑我们的问题是否可以通过使用两点式方法来有效解决，往往是很好的。

In the two-pointer approach, pointers refer to an array’s indexes. By using pointers, we can process two elements per loop, instead of just one.

在双指针方法中，指针指的是一个数组的索引。通过使用指针，我们可以在每个循环中处理两个元素，而不是只有一个。

Common patterns in the two-pointer approach involve:

双指针方法的常见模式涉及。

Two pointers each starting from the beginning and the end until they both meet
One pointer moves at a slow pace while the other pointer moves at a faster pace

Both of the above patterns can help us to reduce the time and space complexity of our problems as we get the expected result in fewer iterations and without using too much additional space.

上述两种模式都可以帮助我们降低我们问题的时间和空间复杂性，因为我们在更少的迭代中得到了预期的结果，并且没有使用太多的额外空间。

Now, let’s take a look at a few examples that will help us to understand this technique a bit better.

现在，让我们看一下几个例子，这将有助于我们更好地理解这种技术。

3. Sum Exists in an Array

3.数组中存在的和

Problem: Given a sorted array of integers, we need to see if there are two numbers in it such that their sum is equal to a specific value.

问题：给定一个经过排序的整数数组，我们需要查看其中是否有两个数字的总和等于一个特定值。

For example, if our input array is [1, 1, 2, 3, 4, 6, 8, 9] and the target value is 11, then our method should return true. However, if the target value is 20, it should return false.

例如，如果我们的输入数组是[1, 1, 2, 3, 4, 6, 8, 9]并且目标值是11，那么我们的方法应该返回true。然而，如果目标值是20，它应该返回false。

Let’s first see a naive solution:

让我们先看看一个天真的解决方案。

public boolean twoSumSlow(int[] input, int targetValue) {

    for (int i = 0; i < input.length; i++) {
        for (int j = 1; j < input.length; j++) {
            if (input[i] + input[j] == targetValue) {
                return true;
            }
        }
    }
    return false;
}

In the above solution, we looped over the input array twice to get all possible combinations. We checked the combination sum against the target value and returned true if it matches. The time complexity of this solution is $O(n^2)$

在上面的解决方案中，我们在输入数组上循环了两次，以获得所有可能的组合。我们根据目标值检查组合的总和，如果匹配则返回true。该解决方案的时间复杂度为 $O(n^2)$ $。$

Now let’s see how can we apply the two-pointer technique here:

现在，让我们看看如何在这里应用两点一线的技术。

public boolean twoSum(int[] input, int targetValue) {

    int pointerOne = 0;
    int pointerTwo = input.length - 1;

    while (pointerOne < pointerTwo) {
        int sum = input[pointerOne] + input[pointerTwo];

        if (sum == targetValue) {
            return true;
        } else if (sum < targetValue) {
            pointerOne++;
        } else {
            pointerTwo--;
        }
    }

    return false;
}

Since the array is already sorted, we can use two pointers. One pointer starts from the beginning of the array, and the other pointer begins from the end of the array, and then we add the values at these pointers. If the sum of the values is less than the target value, we increment the left pointer, and if the sum is higher than the target value, we decrement the right pointer.

由于数组已经被排序，我们可以使用两个指针。一个指针从数组的开头开始，另一个指针从数组的结尾开始，然后我们将这些指针上的数值相加。如果数值之和小于目标值，我们就增加左边的指针，如果数值之和大于目标值，我们就减去右边的指针。

We keep moving these pointers until we get the sum that matches the target value or we have reached the middle of the array, and no combinations have been found. The time complexity of this solution is a significant improvement over our first implementation.

我们不断地移动这些指针，直到我们得到与目标值相匹配的总和，或者我们已经到达数组的中间，并且没有找到任何组合。这个解决方案的时间复杂度为 $O(n)$ $。$ 与我们的第一个实现相比，有很大的改进。

4. Rotate Array k Steps

4.旋转阵列k步数

Problem: Given an array, rotate the array to the right by k steps, where k is non-negative. For example, if our input array is [1, 2, 3, 4, 5, 6, 7] and k is 4, then the output should be [4, 5, 6, 7, 1, 2, 3].

问题：给定一个数组，将该数组向右旋转k步，其中k为非负数。例如，如果我们的输入数组是[1, 2, 3, 4, 5, 6, 7]，k是4，那么输出应该是[4, 5, 6, 7, 1, 2, 3>。

We can solve this by having two loops again which will make the time complexity O(n^2) or by using an extra, temporary array, but that will make the space complexity O(n).

我们可以通过两个循环来解决这个问题，这将使时间复杂度O(n^2)或者使用一个额外的临时数组，但这将使空间复杂度O(n)。

Let’s solve this using the two-pointer technique instead:

让我们改用双指针技术来解决这个问题。

public void rotate(int[] input, int step) {
    step %= input.length;
    reverse(input, 0, input.length - 1);
    reverse(input, 0, step - 1);
    reverse(input, step, input.length - 1);
}

private void reverse(int[] input, int start, int end) {
    while (start < end) {
        int temp = input[start];
        input[start] = input[end];
        input[end] = temp;
        start++;
        end--;
    }
}

In the above methods, we reverse the sections of the input array in-place, multiple times, to get the required result. For reversing the sections, we used the two-pointer approach where swapping of elements was done at both ends of the array section.

在上述方法中，我们对输入数组的部分进行了多次原地反转，以获得所需的结果。为了反转这些部分，我们使用了双指针方法，在数组部分的两端进行元素互换。

Specifically, we first reverse all the elements of the array. Then, we reverse the first k elements followed by reversing the rest of the elements. The time complexity of this solution is

具体来说，我们首先反转数组的所有元素。然后，我们反转前k个元素，再反转其余元素。这个解决方案的时间复杂度是 $O(n)$

5. Middle Element in a LinkedList

5.LinkedList中的中间元素

Problem: Given a singly LinkedList, find its middle element. For example, if our input LinkedList is 1->2->3->4->5, then the output should be 3.

问题：给定一个单一的LinkedList，找出其中间元素。例如，如果我们的输入LinkedList是1->2->3->4->5，那么输出应该是3。

We can also use the two-pointer technique in other data-structures similar to arrays like a LinkedList:

我们还可以在其他类似于数组的数据结构中使用双指针技术，比如LinkedList。

public <T> T findMiddle(MyNode<T> head) {
    MyNode<T> slowPointer = head;
    MyNode<T> fastPointer = head;

    while (fastPointer.next != null && fastPointer.next.next != null) {
        fastPointer = fastPointer.next.next;
        slowPointer = slowPointer.next;
    }
    return slowPointer.data;
}

In this approach, we traverse the linked list using two pointers. One pointer is incremented by one while the other is incremented by two. When the fast pointer reaches the end, the slow pointer will be at the middle of the linked list. The time complexity of this solution is

在这种方法中，我们使用两个指针来遍历链接列表。一个指针递增1，而另一个指针递增2。当快指针到达终点时，慢指针将处于链表的中间位置。该方案的时间复杂度为 $O(n)$ $，而$ $空间复杂度为 O（1）。$

6. Conclusion

6.结语

In this article, we discussed how can we apply the two-pointer technique by seeing some examples and looked at how it improves the efficiency of our algorithm.

在这篇文章中，我们讨论了如何通过看到一些例子来应用双指针技术，并看了它是如何提高我们算法的效率的。

The code in this article is available over on Github.

本文中的代码可在Github上获得。