一道来自字节跳动2019春招研发岗的算法题。

题目介绍

我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工，我提议

  1. 我们在字节跳动大街的 N 个建筑中选定 3 个埋伏地点。
  2. 为了相互照应，我们决定相距最远的两名特工间的距离不超过 D 。

我特喵是个天才! 经过精密的计算，我们从X种可行的埋伏方案中选择了一种。这个方案万无一失，颤抖吧，孔连顺！
……
万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！

请听题：给定 N（可选作为埋伏点的建筑物数）、 D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。
注意：

  1. 两个特工不能埋伏在同一地点
  2. 三个特工是等价的：即同样的位置组合( A , B , C ) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用
1
2
3
数据范围: 0<n,d≤10的6次方
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 128M，其他语言256M

输入描述：

第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)

第二行包含N个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）

输出描述：

一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模

示例1

1
2
3
4
5
6
7
输入例子：
4 3
1 2 3 4
输出例子：
4
例子说明：
可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)

示例2

1
2
3
4
5
6
7
输入例子：
5 19
1 10 20 30 50
输出例子：
1
例子说明：
可选方案 (1, 10, 20)

示例3

1
2
3
4
5
6
7
输入例子：
2 100
1 102
输出例子：
0
例子说明：
没有合适的埋伏方案

解题思路

这道题目的解法往动态规划方向去想，主要是一开始没看清题目就动手，浪费了很多时间。题目中明确说了三个人是等价的，并且不能在同一地点，所以我们只需要考虑三个人的位置，而不需要考虑具体是哪个人在哪个位置。然后要求是最远的两个人之间的距离不超过 D，而当时想当然的认为是每个人之间的距离不超过 D，这样就导致了错误的解法。

正确的解法是，我们只需要考虑三个人的位置，然后我们可以使用双指针来解决这个问题。我们可以使用两个指针，一个指向最左边的人，一个指向最右边的人，使得这两个人之间的距离不超过 D。这样我们就可以得到这三个人的位置的组合数，然后我们可以通过组合数的公式来计算出总的组合数。

这里很尴尬地把排列组合的公式搞错了，导致了错误的解法，正确的公式是： 。在这里 n 是最右边的人到最左边的人的距离，m 是 2，因为我们要选择两个人的位置。所以我们可以得到组合数为： 。

综上，遍历最左边的人的位置，然后找到最右边的人的位置，然后计算组合数，最后将所有的组合数相加，就可以得到最终的结果。

代码实现

这里关键是找到最右边的人的位置，虽然建筑的排列是从小到大的，可以使用二分查找来找到最右边的人的位置，但当时想着简单直接遍历，导致了超时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package main

import (
	"fmt"
)

func main() {
	n := 0
	d := 0

	if cnt, err := fmt.Scan(&n, &d); err != nil || cnt != 2 {
		return
	}

	var buildings []int = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&buildings[i])
	}

	var count int64 = 0
	for i := 0; i < n-2; i++ {
		for j := i+2; j < n && buildings[j]-buildings[i] <= d; j++ {
		}
		j--

		if j-i > 1 {
			count += int64((j - i) * (j - i - 1) / 2)
			// fmt.Println("count:", count)
		}
	}

	fmt.Println(count)
}

本想使用二分查找来找到最右边的人的位置，后来发现其实在查找的时候可以优化，不需要每次都从 i+2 开始查找，而是可以从上一次的位置开始查找，这样可以减少查找的次数，提高效率。

后面提交的时候又卡了一个很大数的测试用例，回过头看题干，发现了这句话：

1
结果可能溢出，请对 99997867 取模

所以需要对结果取模，这样就可以通过了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package main

import (
	"fmt"
)

func main() {
	n := 0
	d := 0

	if cnt, err := fmt.Scan(&n, &d); err != nil || cnt != 2 {
		return
	}

	var buildings []int = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&buildings[i])
	}

	var count int64 = 0
	j := 2
	for i := 0; i < n-2; i++ {
		for ; j < n && buildings[j]-buildings[i] <= d; j++ {
		}
		j--

		if j-i > 1 {
			count += int64((j - i) * (j - i - 1) / 2)
			// fmt.Println("count:", count)
		}
	}

	mod := int64(99997867)
	fmt.Println(count % mod)
}