解决问题的模式

欢迎回到我们关于现代软件工程问题解决的博客系列！

在第 1 部分中，我们探索了频率计数器模式，这是一种通过有效计算元素频率来优化算法的强大技术。如果您错过了或想快速回顾一下，请随时查看后再继续。

在这一部分中，我们将深入研究另一个基本模式：多指针模式。在处理需要同时比较、搜索或遍历多个元素的场景时，这种模式非常有用。让我们探讨一下它是如何工作的，以及在哪里可以应用它来提高代码的效率。

02. 多指针模式

多指针模式是算法设计中使用的一种技术，其中使用多个指针（或迭代器）来遍历数组或链表等数据结构。此模式不依赖单个指针或循环，而是使用两个或多个指针，以不同的速度或从不同的起点移动数据。

示例问题

编写一个名为 sumZero 的函数，它接受 排序 整数数组。该函数应该找到总和为零的第一对。如果存在这样的对，则返回包含这两个值的数组；否则，返回未定义.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

基本解决方案

function sumZero(arr){
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if (arr[i] + arr[j] === 0) {
                console.log(arr[i] + arr[j])
                return [arr[i], arr[j]]
            }
        }
    }
}

时间复杂度 - O(N^2)

使用多指针模式的解决方案

第 1 步：理解问题
我们需要在 **sorted 数组中找到两个加起来为零的数字。由于数组是有序的，我们可以利用这个顺序更有效地找到解决方案。

第 2 步：初始化两个指针
设置两个指针：一个 (left) 从数组开头开始，另一个 (right) 从数组末尾开始。

示例：

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5

第 3 步：计算指针处的值的总和
将左右指针处的值相加即可得到总和

Sum = -4 + 5 = 1

第四步：将总和与零进行比较

• 如果总和大于零：将右指针向左移动一步以减少总和。

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• 如果总和小于零：将左指针向右移动一步以增加总和。

New Sum = -4 + 2 = -2
Sum is -2 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -3
Right Pointer (R): 2

第 5 步：重复该过程
继续移动指针并计算总和，直到它们相遇或找到一对。

New Sum = -3 + 2 = -1
Sum is -1 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -2
Right Pointer (R): 2

总和为零，因此函数返回 [-2, 2]。

如果循环完成而没有找到这样的一对，则返回undefined.

最终代码

function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left < right) {                // Continue until the pointers meet
    const sum = arr[left] + arr[right]; // Calculate the sum of the values at the pointers

    if (sum === 0) {                    // If the sum is zero, return the pair
      return [arr[left], arr[right]];
    } else if (sum > 0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left++;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}

注意：
时间复杂度：O(n) – 该函数非常高效，并且随数组大小线性缩放。
空间复杂度：O(1) – 该函数使用最少的额外内存。

结论

多指针模式是一种强大的技术，用于解决涉及在排序数据结构中搜索、比较或操作元素的问题。通过使用多个相互移动的指针，我们可以显着提高算法的效率，在许多情况下将时间复杂度从 O(n²) 降低到 O(n)。这种模式用途广泛，可以应用于广泛的问题，使其成为优化代码性能的重要策略。

请继续关注我们的下一篇文章，我们将深入探讨滑动窗口模式解决涉及动态数据段的问题的另一个重要工具。这是一种非常有用的模式，可以帮助您轻松解决更复杂的挑战！

以上是解决问题的模式的详细内容。更多信息请关注PHP中文网其他相关文章！