相向双指针

摘要

两数之和的十种变形题
1. 数据结构设计
2. 不同的二元组个数
3. 两数之和小于等于
4. 两数之和大于等于
5. 三角形个数
6. 两数之和最接近
7. 三数之和
8. 三数之和最接近
9. 四数之和
10. K数之和
时间复杂度与循环层数的关系
Partition 型相向双指针
1. 2-Part-Partition vs 3-Part-Partition
2. 彩虹排序算法
3. 通过移0的问题看相向双指针与同向双指针的区别

双指针的类型

背向双指针
- Longest Palindromic Substring 的中心线枚举算法
- 二分法中的 Find K Closest Elements
相向双指针
- Reverse 型（题目不多）
- Two Sum 型（两位数的相关变形题）
- Partition 型（两位数相关变形题）
同向双指针
- 滑动窗口类 Sliding Window
- 快慢指针类 Fast & Slow Pointers

相向双指针

两根指针一头一尾，向中间靠拢直到相遇
时间复杂度 O(n)

Two Sum 型

先修内容中我们已经讲解了双指针的经典题 Two Sum 接下来我们来看这类问题可能的变化

607 · 两数之和 III-数据结构设计

使用 HashMap 的做法

AddNumber - O(1)
FindTwoSum - O(n)

其中 find 函数会输入一个目标和 value

需要 for 循环 HashMap 里的每个 num，检查一下 value - num 是不是也在 HashMap 里，这个过程需要总共 O(n * 1) 的时间

var counter = make(map[int]int)

/
 * @param number: An integer
 * @return: nothing
 */
func add(number int) {
	counter[number]++
}

/
 * @param value: An integer
 * @return: Find if there exists any pair of numbers which sum is equal to the value.
 */
func find(value int) bool {
	for num1 := range counter {
		num2 := value - num1
		wantCnt := 1
		if num1 == num2 {
			wantCnt = 2
		}
		if counter[num2] >= wantCnt {
			return true
		}
	}
	return false
}

57 · 三数之和

统计所有的和为 0 的三元组 (Triples)

func ThreeSum(nums []int) [][]int {
	sort.Ints(nums)
	res := make([][]int, 0)
	for i := range nums {
		if i != 0 && nums[i] == nums[i-1] {
			continue
		}
		findTwoSum(nums, i, &res)
	}
	return res
}

func findTwoSum(nums []int, idx int, res *[][]int) {
	left := idx + 1
	right := len(nums) - 1
	target := -nums[idx]
	for left < right {
		tmp := nums[left] + nums[right]
		if tmp < target {
			left++
		} else if tmp > target {
			right--
		} else {
			*res = append(*res, []int{nums[idx], nums[left], nums[right]})
			left++
			right--
			for left < right && nums[left] == nums[left-1] {
				left++
			}
		}
	}
}

382 · 三角形计数

使用双指针算法。 for 循环最大边的位置 i，接下来的任务就是在 0 ~ i-1 之间找到两数之和 > nums[i]

func triangleCount(nums []int) int {
	var ans int
	sort.Ints(nums)
	for i := len(nums) - 1; i > 1; i-- {
		for left, right := 0, i-1; left < right; {
			if nums[left]+nums[right] <= nums[i] {
				left++
			} else {
				ans += right - left
				right--
			}
		}
	}
	return ans
}

58 · 四数之和

在数组中求 a + b + c + d = target 的所有四元组固定两个点，然后用双指针的做法，扫描一下后续数组，记录答案即可。

func FourSum(nums []int, target int) [][]int {
	sort.Ints(nums)
	res := make([][]int, 0)
	for i := 0; i < len(nums)-1; i++ {
		if i != 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < len(nums)-1; j++ {
			if j != i+1 && nums[j] == nums[j-1] {
				continue
			}

			left := j + 1
			right := len(nums) - 1
			for left < right {
				tmp := nums[i] + nums[j] + nums[left] + nums[right]
				if tmp < target {
					left++
				} else if tmp > target {
					right--
				} else {
					res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
					left++
					right--
					for left < right && nums[left] == nums[left-1] {
						left++
					}
				}
			}
		}
	}
	return res
}

Partition 型

31 · 数组划分

数组严格的分为 < k 的部分和 >= k 的部分

func PartitionArray(nums []int, k int) int {
	if len(nums) == 0 {
		return 0
	}
	left, right := 0, len(nums)-1
	for left <= right {
		for left <= right && nums[left] < k {
			left++
		}
		for left <= right && nums[right] >= k {
			right--
		}
		if left <= right {
			nums[left], nums[right] = nums[right], nums[left]
			left++
			right--
		}
	}
	return left
}

Partition Array vs Quick Sort / Quick Select

目标不同

Partition Array 需要严格的左半部分 < k，右半部分 >= k

Quick Sort / Quick Select 只需要左半部分整体 <= 右半部分即可

如果 Quick Sort / Quick Select 把 == pivot 的严格划分到左边或者右边，会导致极端情况发生从而时间复杂度很容易退化到 O(n^2)，如排序 [1, 1, 1, 1, 1]

Partition Array

为什么用 left <= right 而不是 left < right?

如果用 left < right, while 循环结束在 left == right 此时需要多一次 if 一句判断 nums[left] 到底是 < k 还是 >=k 因此使用 left <= right 可以省去这个判断

// Partition类双指针算法模板
for left <= right {
	for left <= right && nums[left] < k {
		left++
	}
	for left <= right && nums[right] >= k {
		right--
	}
	if left <= right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

Quick Sort / Quick Select

for left <= right {
	for left <= right && nums[left] < pivot {
		left++
	}
	for left <= right && nums[right] > pivot {
		right--
	}
	if left <= right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

独孤九剑 —— 破鞭式

时间复杂度与最内层循环主体的执行次数有关，与有多少重循环无关

539 · 移动零

最少操作数

func MoveZeroes(nums []int) {
	left, right := 0, 0
	for right < len(nums) {
		if nums[right] != 0 {
			nums[left] = nums[right]
			left++
		}
		right++
	}
	for ; left < len(nums); left++ {
		if nums[left] != 0 {
			nums[left] = 0
		}
	}
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。