字节跳动 —— 建筑物组合(滑动窗口+溢出问题)

原题描述： 

题目精炼：

   给定N个建筑物的位置和一个距离D，选取3个建筑物作为埋伏点，找出所有可能的建筑物组合，使得每组中的建筑物之间的最大距离不超过D。最后，输出不同埋伏方案的数量并对99997867取模。

识别问题：

   由于此题的建筑物是一个单调递增的数组（单调性），并且使用“同向双指针”来维护一段区间，保证（判断条件）：

        1）right - left +1 >= 3
        2）buildings[right] - buildings[left] <= D
        3）right < buildings.length 或者 left < buildings.lengrh - 2

   因此，我们可以使用“滑动窗口”来求解。

滑动窗口解题思路：

1）左右指针初始化

int left = 0;
int right = 2;

2）满足条件进窗口

注意，要先判断right是否小于数组长度，否则会越界

while(right < buildings.length && buildings[right] - buildings[left] <= D){right++;
}

3）更新结果

此处涉及到求解组合数量问题，为了防止一段区间内，子集重复的问题，每次以buildings[left]为基准，在剩余的buildings中选取两个进行组合，公式为

但是，此处涉及到两个很大的整数相乘，会出现溢出的问题，因此我们可以使用更大的整数类型，将n*(n-1)转换为long类型，并对每次累加后的结果%99997867 防止溢出。

int n = right - left - 1;
long p =((long)n *(n-1))>>1;
count =(count + p)%99997867;

当因为right>=buildings.length而跳出循环时，说明此时没有更大的值了，收集完结果后要对right--，使得right始终停留在最右边界，从而可以继续判断，等待left缩小窗口

if(right >= buildings.length){right--;
}

4）出窗口

left++;

其中，进窗口，更新结果，出窗口是一个不断循环的过程，因此，最终代码为：

import java.util.Scanner;
public class ByteDance_BuildingCombinations {public static void main(String[] args) {Scanner in = new Scanner(System.in);int N = in.nextInt();int D = in.nextInt();int[] buildings = new int[N];for (int i = 0; i < N; i++) {buildings[i] = in.nextInt();}long count = slide(buildings,D);System.out.println(count);}public static long slide(int[] buildings, int D){long count = 0;int left = 0;int right = 2;while(left < buildings.length - 2){while(right < buildings.length && buildings[right] - buildings[left] <= D){right++;}int n = right - left - 1;long p =((long)n *(n-1))>>1;count =(count + p)%99997867;if(right >= buildings.length){right--;}left++;}return count;}
}