数字距离

数字距离的公式化处理：半开区间与闭区间的长度计算，边界语义统一。

  • 基础概念
  • 区间长度

一句话算法

两个整数相减得到的是半开区间长度；如果右端点也要算进去，就再加 1。

问题模型

在数轴上有两个整数位置 ii 和 jj，且 i≤ji \le j。常见问题有两种：

  1. 从 ii 到 jj，包含 ii，不包含 jj，有多少个整数位置？
  2. 从 ii 到 jj，同时包含 ii 和 jj，有多少个整数位置？

例如 3→93 \to 9：

  • [3,9)[3,9) 包含 3,4,5,6,7,8，长度是 6。
  • [3,9][3,9] 包含 3,4,5,6,7,8,9，长度是 7。

核心直觉

j - i 计算的是从 i 走到 j 需要跨过多少条边，不是点的数量。

3 -- 4 -- 5 -- 6 -- 7 -- 8 -- 9

从 3 到 9 一共跨过 6 条边，所以：

∣[3,9)∣=9−3=6 |[3,9)| = 9 - 3 = 6

如果把右端点 9 这个点也算进去，就要再加 1：

∣[3,9]∣=9−3+1=7 |[3,9]| = 9 - 3 + 1 = 7

算法步骤

  1. 半开区间 [i,j)：直接返回 j - i。
  2. 闭区间 [i,j]：返回 j - i + 1。
  3. 相对位置：
    • 不包含当前位置，向右第 n 个位置是 pos + n。
    • 包含当前位置，向右第 n 个位置是 pos + n - 1。
    • 向左同理，把方向改成 -1。

算法证明

从 ii 到 jj，相邻整数之间的边是：

(i,i+1),(i+1,i+2),⋯ ,(j−1,j) (i,i+1),(i+1,i+2),\cdots,(j-1,j)

边数正好是 j−ij-i，所以半开区间长度是 j−ij-i。

闭区间比半开区间多包含右端点 jj，因此长度为：

j−i+1 j-i+1

复杂度分析

所有计算都是常数次整数运算。

  • 时间复杂度：O(1)O(1)。
  • 空间复杂度：O(1)O(1)。

代码实现

cpp 
        
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

        #include <bits/stdc++.h>
using namespace std;

// [i, j) 的长度：包含 i，不包含 j。
int distance_exclude_right(int i, int j) {
    return j - i;
}

// [i, j] 的长度：同时包含 i 和 j。
int distance_include_right(int i, int j) {
    return j - i + 1;
}

struct RelativePosition {
    int pos;

    // 从当前位置向 dir 方向走 n 步，不把当前位置算作第 1 个位置。
    int move_exclude_current(int n, int dir) const {
        return pos + n * dir;
    }

    // 从当前位置向 dir 方向数 n 个位置，把当前位置算作第 1 个位置。
    int move_include_current(int n, int dir) const {
        return pos + (n - 1) * dir;
    }

    int next_exclude_current(int n) const {
        return move_exclude_current(n, 1);
    }

    int next_include_current(int n) const {
        return move_include_current(n, 1);
    }

    int prev_exclude_current(int n) const {
        return move_exclude_current(n, -1);
    }

    int prev_include_current(int n) const {
        return move_include_current(n, -1);
    }
};

int main() {
    cout << distance_exclude_right(3, 9) << '\n';
    cout << distance_include_right(3, 9) << '\n';

    RelativePosition p{10};
    cout << p.next_exclude_current(3) << '\n';
    cout << p.next_include_current(3) << '\n';
    return 0;
}

测试用例

代码中的演示输出：

6
7
13
12

含义：

  • [3,9) 长度为 6。
  • [3,9] 长度为 7。
  • 从 10 向右走 3 步且不包含当前位置，到 13。
  • 从 10 向右数第 3 个位置且包含当前位置，到 12。

应用分类详解

数字距离的本质是统一“区间端点是否被包含”的语义。很多边界错误都来自这里。

一、数组区间长度

典型模式： 需要计算 [l,r] 或 [l,r) 的元素个数。 识别信号： 题面或代码中同时出现 l、r、长度、窗口大小。 核心建模： 先确定区间是闭区间还是半开区间，再写长度公式。

应用场景 经典题目 核心思路
前缀和区间 本书前缀和教程 闭区间 [l,r] 长度是 r-l+1
滑动窗口 本书双指针教程 常用半开区间 [l,r)，长度是 r-l

二、相对位置推导

典型模式： 从某个位置向前或向后数第几个。 识别信号： 出现“前 k 个”“后 k 个”“包含当前位置”。 核心建模： 包含当前位置就少走一步，不包含当前位置就走满 k 步。

应用场景 经典题目 核心思路
环形数组位置 约瑟夫类问题 把“数几个”和“走几步”区分开
窗口边界移动 单调队列题 根据窗口是否包含端点确定过期条件

经典例题

  1. luogu-P1886 滑动窗口边界题。判断元素是否过期时要清楚窗口长度和端点含义。

  2. 本书前缀和教程 闭区间和、半开区间和的下标公式都依赖数字距离。