双指针

双指针算法是解决数组和链表问题的一种常用技巧,它主要用于减少不必要的计算,降低问题的复杂度。双指针算法通常有以下几种类型:

  1. 快慢指针:主要用于解决链表中的问题,如检测链表中的循环。
  2. 左右指针:主要用于有序数组或字符串的问题,如二分查找、合并两个有序数组。
  3. 对撞指针:主要用于计算有序数组中的两数之和、三数之和等问题。

双指针算法的通用思路包括:

  • 确定指针的含义:在开始编写代码之前,你需要明确每个指针的作用,比如一个指针用来遍历,另一个指针用来检查条件等。
  • 正确移动指针:根据问题的需要,决定指针是向前移动还是向后移动,以及何时移动指针。
  • 维护指针状态:在移动指针的过程中,需要维护和更新指针的状态,以及它们之间的关系。
  • 循环结束条件:明确循环结束的条件,确保程序不会进入无限循环,同时能够在正确的时候停止。

下面是一些使用 Go 语言实现的双指针算法的例子:

例 1:反转字符串中的元音字母

func reverseVowels(s string) string {
    vowels := "aeiouAEIOU"
    bytes := []byte(s)
    left, right := 0, len(s)-1

    for left < right {
        for left < right && !strings.ContainsRune(vowels, rune(bytes[left])) {
            left++
        }
        for left < right && !strings.ContainsRune(vowels, rune(bytes[right])) {
            right--
        }
        bytes[left], bytes[right] = bytes[right], bytes[left]
        left++
        right--
    }

    return string(bytes)
}

例 2:有序数组的 Two Sum

func twoSum(numbers []int, target int) []int {
    left, right := 0, len(numbers)-1

    for left < right {
        sum := numbers[left] + numbers[right]
        if sum == target {
            return []int{left + 1, right + 1}
        } else if sum < target {
            left++
        } else {
            right--
        }
    }

    return []int{-1, -1} // 如果没有找到解
}

例 3:移除元素

func removeElement(nums []int, val int) int {
    left := 0

    for right := 0; right < len(nums); right++ {
        if nums[right] != val {
            nums[left] = nums[right]
            left++
        }
    }

    return left
}

在使用双指针时,关键是要理解如何移动指针以及如何根据问题的需求来更新指针的状态。每个问题可能需要不同的策略,但上述提供的示例代码可以作为一个起点来解决类似的问题。