线性表的定义和基本操作

线性表的定义

线性表是具有相同数据类型 n 个数据元素的有限序列，其中 n 为表长，当 n = 0 时线性表是一个空表

以 L 命名线性表，其表示为 $L = (a_{1}, a_{2}, \dots, a_{n})$ ， $a_{1}$ 叫表头元素， $a_{n}$ 叫表尾元素

除第一个元素外，每个元素都有一个直接前驱；除最后一个元素外，气态元素都有一个直接后继

线性表有以下特点：

表中元素的个数有限
表中元素具有逻辑上的顺序性，表中元素有先后次序
表中元素都是数据元素，每个元素都是单个元素
表中元素的数据类型相同，即元素的大小相同
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑内容

注意：线性表是逻辑关系，表示元素间的逻辑关系；顺序表和链表是存储关系，表示元素的物理关系

线性表的基本操作


InitList(L);  // 初始化表

Length(L);  // 求表长

LocateElem(L, e);  // 按值查找位置

GetElem(L, i);  // 按位置查找值

ListInsert(&L, i, e);  // 插入操作

ListDelete(&L, i, &e);  // 删除操作, e 是返回删除元素

PrintList(L);  // 输出操作，按前后顺序输出线性表的所有值

Empty(L);  // 判空操作

DestroyList(&L);  // 销毁操作，回收线性表的内存

线性表的顺序表示

顺序表的定义

顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素，使得两个元素在逻辑和物理上都相邻

线性表中的任一数据元素都可以随机存储，线性表的顺序存储结构是一种随机存储结构

考点追踪：顺序表上操作的时间复杂度分析（高频：2023）与顺序表的应用（真题热点：2010、2011、2018、2020、2025）

顺序表在基础概念中非常容易出现和数组下标混用的低级错误！

注意：位序与数组下标

线性表中元素的位序从 1 标志开始，而数组中元素的下标从 0 开始。为什么判断插入位置时使用 length+1，而移动元素的 for 循环中使用 length？因为合法插入位置包括第 $n + 1$ 位，但移动元素时最多从第 $n$ 位开始后移。

静态分配时，一旦空间占满再加入新数据就会溢出导致程序崩毁，存储类型描述为：


#define MaxSize 50

typedef struct {

    ElemType data[MaxSize];

    int length;

} SqList;

动态分配时，一旦数据空间占满，就另外开辟一块更大的存储空间，以替换原来的空间，存储类型描述为：

c++


#define InitSize 100

typedef struct {

    ElemType *data;

    int MaxSize, length;

} SeqList;



L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);  // C 的内存分配

L.data = new ElemType[InitSize];  // C++ 的内存分配




> [!WARNING] 注意：动态分配并非链式表示

> 动态分配并不是链式存储，它同样属于顺序存储结构！其物理结构没有变化，依然支持随机存取，只是存储空间的大小可以在运行时动态调整。



**顺序表的特点：**



1. 顺序表最主要的特点是随机访问，给了首地址和元素序号可在 O(1) 内找到元素

2. 顺序表的存储密度高，每个结点只存储数据元素

3. 顺序表逻辑及上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素



## 顺序表上基本操作的实现



### 插入操作



```c

bool ListInsert(SqList &L, int i, ElemType e) {

    if (i < 1 || i > L.length + 1)  // 验证 i 是否越界

        return false;

    if (L.length >= Maxsize)  // 存储空间是否还有空位

        return false;

    for (int j = L.length; j >= i; j--)  // 将第 i 个元素后移

        L.data[j] = L.data[j - 1];

    L.data[i - 1] = e;  // 把 e 插入位置 i

    L.length++;  // 长度加一

    return true;

}

平均情况：每个位置移动的次数加起来除以位置的个数， $\frac{1}{n + 1} \sum_{i = 1}^{n + 1} (n - i + 1) = \frac{n}{2}$ ，时间复杂度为 O(n)

核心结论：时间复杂度层级速记 (2025 必备)

常数阶 $O (1)$ : 与规模无关。

对数阶 $O (\log n)$ : 常见于折半查找、二叉搜索树、分治法的一侧。

线性阶 $O (n)$ : 遍历数组、单链表扫描。

线性对数阶 $O (n \log n)$ : 快速排序、归并排序、堆排序的平均情况。

平方阶 $O (n^{2})$ : 嵌套循环（冒泡、直接插入排序）。

$O (1) < O (\log_{2} n) < O (n) < O (n \log_{2} n) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!) < O (n^{n})$

考点追踪：分析算法的时间复杂度（高频：2010—2021、2025）

插入/删除：最好 O(1)，最坏 O(n)，平均 O(n)。空间复杂度 O(1)（原地工作）。

按序查找（GetElem）：直接通过下标访问，O(1)。这是顺序表唯一的随机存取特性。

按值查找（LocateElem）：无序时 O(n)；若表有序，可降至 $O (\log n)$ （折半查找）。

易错点：位序与下标（高频）

在算法设计题中，若题目要求在第 $i$ 个位置操作，代码需转化为数组下标 i-1。插入合法范围 $[1, n + 1]$ ，删除合法范围 $[1, n]$ 。分不清 0 与 1 的起始会导致整题丢分。

综合应用题

删除表内所有为 x 的元素

问题：对长度为 n 的顺序表 L，编写一个时间复杂度为 O(n)、空间复杂度为 O(1) 的算法，该算法删除线性表中所有值为 x 的数据元素


void deleteElem(SqList &L, ElemType x){

    int k = 0;

    for (int i = 0; i < L.length; i++)

        if (L.data[i] != x)

            L.data[k++] = L.data[i];

    L.length = k;

}

数组中的两个顺序表位置互换

思想：先整个数组逆置，这时 $L = (b_{n}, \dots, b_{1}, a_{n}, \dots, a_{1})$ 再将 A 和 B 内部分别逆置就有 $L = (b_{1}, \dots, b_{n}, a_{1}, \dots, a_{n})$


void Reverse(int []array, int left, int right){

    int mid = (right - left) / 2;

    int tmp;

    for (int i = 0; i <= mid; i++){

        tmp = array[left + i];

        array[left + i] = array[right - i];

        array[right - i] = tmp;

    }

}



void Exchange(int []array, int m, int n){

    int len = m + n;

    Reverse(array, 0, len - 1);

    Reverse(array, 0, n - 1);

    Reverse(array, n, len - 1);

}

时间复杂度 O(n)，空间复杂度 O(1)

方法 2：使用 a 和 b 的后半部分交换，就有 $L = (b_{m - n + 1}, \dots, b_{m}, b_{1} \dots, b_{m - n}, a_{1}, \dots, a_{n})$ ，就变成 $(b_{2}, b_{1}, a)$ ，反复换几次就可以，最后 $b_{1}$ 和 $b_{2}$ 长度相等直接交换就行，这里可以思考直接使用最大公约数的解法

两个长度相同数组的联合中位数

问题：有两个长度一样的数组，求它们合并后的中位数，是中间两个数中的较小值

思想：设 a 和 b 是 A 和 B 的中位数

当 a < b 时，a 的左半部分已经无缘中位数，舍去，因为即使 b 的左半部分都过来中位数也是 a；b 的右半部分也一样

当 b > a 时，舍去 b 的左半和 a 的右半

当 b = a 时，显然中位数相等，那么这就是全部的中位数

当舍去直到自己时，中位数就是 a 和 b 间的最小值

注意：这种算法只适合两个长度相同的数组


int MiddleSearch(int A[], int B[], int n){

    int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;

    // s1 == d1 舍去到只剩下自己

    while(s1 != d1 || s2 != d2){

        m1 = (s1 + d1) / 2;

        m2 = (s2 + d2) / 2;

        if (A[m1] == B[m2])  // 当两个中位数一样时，即使全部的中位数

            return A[m1];

        if (A[m1] < B[m2]){

            // 元素的个数为奇数

            if ((s1 + d1) % 2 == 0){

                // 奇数的话需要保留中点

                s1 = m1;

                d2 = m2;

            } else{

                // 偶数的话把整个部分都舍去了

                s1 = m1 + 1;  // 舍去左边，因为中点在左边，所以加一

                d2 = m2;  // 舍去右边不包括中点

            }

        } else{

            if ((s2 + d2) % 2 == 0){

                d1 = m1;

                s2 = m2;

            } else{

                d1 = m1;

                s2 = m2 + 1;

            }

        }

    }

    return A[s1] < B[s2] ? A[s1] : B[s2];

}

时间复杂度 $O (\log_{2} n)$ ，空间复杂度 O(1)

序列的主元素

问题：当一个元素在序列中出现的次数超过一半就把他叫做序列的主元素，求序列是否存在主元素

思想：利用超过一半才叫主元素的特点，使用计数 Count

扫描序列，将第一个数保存到 Elem 中，若下一个数仍是 Elem 计数加一，否则减一；当计数减到零时，将下一个数保存到 Elem 中

完成后再次扫描序列，统计记录的数的个数


int Majority(int A[], int n){

    int i, count = 1, c = A[0];

    for (i = 1; i < n; i++){

        if (A[i] == c) count++;  // 增加该元素的计数

        else if (count > 0) count--;  // 有计数时建设计数

        else {  // 没有时更换计数元素

            count = 1;

            c = A[i];

        }

    }

    if (count > 0)

        for (i = count = 0; i < n; i++)  // 统计元素出现的次数

            if (A[i] == c)

                count++;

    if (count > n / 2) return c;

    else reutrn -1;

}

时间复杂度 O(n)，空间复杂度 O(1)

三元组的最短距离

问题：定义三元组的距离 D = |a - b| + |b - c| + |c - a|

给定 3 个非空整数集合，按升序分别存储在 3 个数组中

需要计算并输出所有可能的三元组中的最小距离

思想：假设一条 x 轴，有三个点 a, b, c 假设 $a \leq b \leq c$ 那么它们距离其实就是 $2 | c - a |$ 那么只要缩小它们的距离就好了

不妨让 a 增加看一下是否变得更短了，因为 c，b 增加只会变更长或者不变

因此我们设置整数存储最短距离 D_m，然后计算距离，比最短距离短就修改最短距离

然后让最小的值的那个数组索引加一，相当于让 a 增加，在次计算距离直到全部迭代


int abs(int a){

    return a >= 0 ? a : -a;

}



bool min(int a, int b, int c){

    if (a <= b && a <= c) return true;

    return false;

}



int FindMinofTrip(int A[], int n, int B[], int m, int C[], int p){

    int minD = 0x7fffffff, D;

    int i = 0, j = 0, k = 0;

    while (i < n && j < m && k < p && minD > 0){

        D = abs(A[i] - B[j]) + abs(B[j] - C[k]) + abs(C[k] - A[i]);

        if (D < minD) minD = D;

        if (min(A[i], B[j], C[k])) i++;

        else if (min(B[j], A[i], C[k])) j++;

        else k++;

    }

    return minD;

}

时间复杂度 O(n)，空间复杂度 O(1)

线性表的链式表示

链式存储线性表时，不要求逻辑上相邻的元素在物理位置上也相邻，它通过链建立数据元素之间的关系

插入和删除操作不需要移动元素，只需修改指针，但也失去顺序表可随机存储的优点

单链表

单链表的定义

线性表的链式存储又称单链表，对于每个链表结点，除了存储自身数据外，还需存储指向其后继的指针

单链表的结点结构如下，其中 data 为数据域，存放数据；next 为指针域，存放后继结点的指针：


typedef struct LNode{

    ElemType data;  // 数据域

    struct LNode *next;  // 指针域

}LNode, *LinkList;

单链表可以解决顺序表需要大量连续存储的缺点，但多加了指针域也会浪费空间

而且单链表不能直接找到表中特定的点，需要从头遍历依次查找

头指针和头结点：头指针是指向第一个结点的指针，为了操作方便会带有头结点，即拿一个空结点做头；同样是表空操作，如果只有头指针 head == NULL，如果带了头结点 head->next == NULL

引入头结点后，可以带来两个优点（操作方便）：

有头结点后第一个位置上的操作和在表的其他位置的操作一致，无需特殊处理
无论表是否为空，头指针都指向非空结点，空表与非空表处理统一

单链表上基本操作的实现

采用头插法建立单链表

头插法就是从空表开始，把每一个结点都插入表头


LinkList ListHeadInsert(LinkList &L){

    LNode *s;

    int x;

    L = (LinkList)malloc(sizeof(LNode));  // 创建头结点

    L -> next = NULL;

    scanf("%d", &x);

    while (x != 9999) {

        s = (LNode *)malloc(sizeof(LNode));  // 创建新结点

        s -> data = x;

        s -> next = L -> next;  // 把旧结点链入新结点

        L -> next = s;  // 设置新结点为表头

        scanf("%d", &x);

    }

    return L;

}

采用头插法建立单链表时，读取数据的顺序与生成的链表中的元素的顺序是相反的，时间复杂度是 O(n)

采用尾插法建立单链表

尾插法是把每一个结点都插入表尾，因此需要一个表尾指针，时间复杂度是 O(n)


LinkList ListTailInsert(LinkList &L){

	int x;

	L = (LinkList)malloc(sizeof(LNode));

	LNode *s, *r = L;

	scanf("%d", &x);

	while(x != 9999){

		s = (LNode*)malloc(sizeof(LNode));

		s -> data = x;

		r -> next = s;  // 把元素插入表尾

		r = s;  // 指向新的表尾

		scanf("%d", &x);

	}

	r -> next = NULL;

	return L;

}

按序号查找结点值

从第一个结点出发，按照指针域依次迭代，直到找到第 i 个结点，时间复杂度是 O(n)


LNode *GetElem(LinkList L, int i){

	int j = 1;

	LNode *p = L -> next;

	if(i == 0)

		return L;

	if(i < 1)

		return NULL;

    // 迭代查找位置为 i 的结点，但 i 超长就只能返回 NULL

	while(p && j < i){

		p = p -> next;

		j++;

	}

	return p;

}

按值查找表结点

从第一个结点出发，依次比较数据域的值，若值相等返回结点指针，没有返回 NULL，时间复杂度是 O(n)


LNode *LocateElem(LinkList L, ElemType e){

	LNode *p = L -> next;

	while(p != NULL && p -> data != e)  // 查找数据域为 e 的结点

		p = p -> next;

	return p;  // 找到返回指针，否则返回 NULL

}

插入结点操作

插入结点首先要找到前一个结点，然后判断结点是否合法，最后再插入，时间复杂度 O(n)


bool ListInsert(LinkList L, int i, ElemType e){

	LinkList p = GetElem(L, i - 1);  // 拿到前一个结点

	if(NULL == p) {  // 检验合法性

		return false;

	}

    // 插入

	LinkList s = (LNode*)malloc(sizeof(LNode));

	s -> data = e;

	s -> next = p -> next;

	p -> next = s;

	return true;

}

q = p -> next;

p -> data = q -> data; // 等于下个结点的数据域

p -> next = q -> next; // 删除下个结点

free(q);

考点追踪：单链表操作技巧（2016、2025）

头插法（逆序）：常用于链表逆置、多项式相加。

尾插法（正序）：必须维护一个尾指针 r。

前插操作：若只给出 *p 指针，可通过交换 *p 与 *s 的 data 变相实现（O(1)）。

删除 p 结点：若只给出 *p 指针，可通过复制后继结点 data 后删除后继变相实现（O(1)），注意 p 是尾结点时无法使用此法。

注意：头结点与判空

带头结点：判空为 L->next == NULL。

不带头结点：判空为 L == NULL。

在算法设计中，统考真题默认多为带头结点，除非显式说明。

核心结论：单链表常用操作复杂度

头插法/尾插法建立： $O (n)$ 。

按序号查找/按值查找： $O (n)$ 。

插入/删除节点： $O (1)$ (已知指针且非尾删) 或 $O (n)$ (需先查找)。

求表长操作

求表长是计算单链表中数据结点的个数，需要从第一个开始向下遍历，每遍历一个计数加一

当访问到空结点的时候计数就是表的长度，时间复杂度是 O(n)

双链表

双链表结点有两个指针 prior 和 next，分别指向前驱和后继，类型的描述如下：


typedef struct DNode{

	ElemType data;  // 数据域

	struct DNode *prior, *next;  // 前指针和后指针

}DNode, *DLinkList;

由于添加了前驱指针所以访问前一个结点是时间复杂度变为 O(1)

仅添加了一个前驱指针，因此只在插入和删除上与单链表有较大的区别

双链表的插入操作

在双链表插入中，不仅要调整与后继结点的关系，还要调整与前驱结点的关系


bool DListFrontInsert(DLinkList DL,int i,ElemType e){

	DLinkList p = GetElem(DL, i - 1);  // 获取前驱值

	if(NULL == p)  // 验证前驱合法性

		return false;

	DLinkList s = (DNode*)malloc(sizeof(DNode));

	s -> data = e;

	s -> next = p -> next;  // 调整和后继的关系

    if (p -> next != NULL)

		p -> next -> prior = s;

	s -> prior = p;  // 调整和前驱的关系

	p -> next = s;

	return true;

}

双链表的删除操作

双链表删除和单链表差不多，要注意调整后继的指针要指向前驱


bool DListDelete(DLinkList DL, int i){

	DLinkList p=GetElem(DL, i - 1);  // 拿到前驱

	if(NULL == p)  // 验证合法性

		return false;

	DLinkList q;

    // 删除结点

	q = p -> next;

	if(q == NULL) return false;

	p -> next = q -> next;

	if(q -> next != NULL)  // 比单链表多的一步

		q -> next -> prior = p;

	free(q);

	return true;

}

循环链表

循环单链表

循环单链表和单链表的区别：表中最后一个结点的指针指向头结点，从而形成一个环

循环单链表的判空条件是头结点的指针是否等于头指针

循环单链表通常不设头指针而设尾指针，因为 r -> next 就是头指针

循环链表可以从任一结点开始遍历整个链表，它的插入和删除操作和单链表基本一样

注意：即使有尾指针，删除尾结点时间复杂度一样是 O(n)，因为要拿到尾结点的前驱

核心结论：循环单链表 (2025 考点)

判空：L->next == L。

特长：若设有尾指针 rear，访首元节点 (rear->next->next) 和访尾节点 (rear) 均为 $O (1)$ 。

循环双链表

循环双链表与循环单链表不同的是，除了尾结点的 next 要指向头结点，它头结点的 prior 还要指向表尾

当循环双链表为空表时，其头结点的 prior 和 next 都等于头指针

静态链表

静态链表借助数组来描述线性表的链式存储结构，结点也有数据域和指针域

但静态链表的结点的指针域存放的是数组的下标，是相对地址，又称游标

因为是由数组实现的，所以和顺序表一样也要预先分配一块连续的内存空间


#define MaxSize 50

typedef struct {

    ElemType data;  // 存储的数据

    int next;  // 下一个元素的数组下标

} SLinkList[MaxSize];

静态链表以 next == -1 作为结束标志，它的插入删除、动态链表一样只需要修改指针，但总的来说没动态链表方便

在一些不支持指针的高级语言中，这是一种链表的巧妙的设计方法

顺序表和链表的比较

存取（读写）方式：顺序表可以顺序存取和随机存取，但链表只能顺序存取
逻辑结构和物理结构：
1. 顺序存储时，逻辑相邻的元素对应物理存储位置也相邻
2. 链式存储时，逻辑相邻的元素，物理存储位置不一定相邻，逻辑关系是通过指针链接表示
查找、插入、删除操作：
1. 按值查找时，无序两者都需要 O(n)；有序时顺序表仅需要 $O (l o g_{2} n)$
2. 按序号查找时，顺序表可随机访问 O(1)，链表要迭代 O(n)
3. 插入和删除时，顺序表平均要移动半个表的元素，而链表仅修改相关指针
空间分配：
1. 顺序存储在静态分配时，存储满了就会溢出，因此需要预先分配足够的存储空间；动态分配时，需要移动大量元素，会导致操作效率低，没有足够的连续空间时还会分配失败
2. 链式存储就只需要在使用时分配，操作灵活、高效

取舍顺序表和链表

通常较稳定的线性表选择顺序存储，频繁插入、删除操作时选择链式存储

核心结论：顺序表 vs 链表深度对比

| 特性 | 顺序表 (Sequential) | 链表 (Linked) |

| :--- | :--- | :--- |

| 存取方式 | 随机存取 O(1) | 顺序存取 O(n) |

| 查找性能 | 有序时 $O (\log n)$ | 始终 O(n) |

| 插入/删除 | 大量移动 O(n) | 修改指针 O(1)* |

| 存储分配 | 静态/动态需连续空间 | 灵活分散空间 |

| 存储密度 | 高 (100%) | 低 (需存指针) |

*注意：链表插入/删除虽然修改指针是 O(1)，但若需查找到位，总时间仍为 O(n)。但在已知指针位置的情况下，链表有绝对优势。

综合应用题

递归删除链表中值为 x 的结点

思想：

当 L 为 NULL 时，迭代完链表退出

当 L 的数据域等于 x 把 L 删了，递归下一个结点

当 L 的数据域不等于 x 时直接递归下一个结点


void Delete(LinkList &L, ElemType e){

    LNode *p;

    if (L == NULL) return;

    if (L -> data == e) {

        p = L;

        L = L -> next;  // 注意这个 L 的类型是引用类型，会修改原链表的指针域

        free(p);

        Delete(L, e);

    } else Delete(L -> next, e);

}

链表是否有环

问题：判断一个链表是否有环，如果有，找出环的入口并返回，否则返回 NULL

思想：

设快慢两个指针 fast、slow，fast 每次走两步，slow 每次走一步，当它们碰头了就表示有环

接下来就是求环的入口了，设头结点到环入口距离为 a，环长为 r

当 slow 走到环入口时，fast 在环中的位置是 a % r，fast 与 slow 的距离是 r - a % r

那么它们碰面时的在环中的位置是，r - a % r，考虑到 (a + r - a % r) % r = 0

所以在碰面的地方再走 a 就到达入口了

因此可设置两个指针，一个指向 head 一个指相遇点，同时移动，相交就是入口点


LNode *FindLoopStart(LNode *head) {

    LNode *fast = head, *slow = head;  // 设置快慢两指针

    while(fast != NULL && fast -> next != NULL) {

        slow = slow -> next;

        fast = fast -> next -> next;

        if (slow == fast) break;  // 相遇

    }

    if (fast == NULL || fast -> next == NULL) 

        return NULL;  // 没有环

    LNode *p1 = head, *p2 = slow;  // 分别指向开始点和相遇点

    while (p1 != p2) {

        p1 = p1 -> next;

        p2 = p2 -> next;

    }

    return p1;  // 返回入口点

}

会做的考研题

求链表倒数第 k 结点

问题：带头结点的单链表，查找倒数第 k 个位置上的结点

思想：设置 p、k 两个变量，p 指针沿链表移动，当 p 移动到第 k 个结点时，q 开始和 p 同步移动，当 p 移动到最后一个结点时，q 就是倒数第 k 个结点

两个单链表的共同结点

问题：采用带头结点的单链表保存单词，当两个单词有共同后缀时可共享后缀存储空间，求共同后缀的起始位置

思想：如果两个链表有公共结点，那么透视图就应该是 Y 形的，公共结点后面的结点都是重合的

我们可以求出两个链表的长度，并取出它们的差，让较长的那个跳过一些结点留下和较短的一样长的结点

然后两个一起迭代，直到两个结点一样进行返回，就像下面

loading -> ading -> ing

being -> being -> ing

去绝对值相等的重复元素

问题：用单链表保存 m 个整数，且 $| d a t a | \leq n$ 数据域的数据的绝对值小于 n，现需要删除绝对值相等的数据，仅保留第一次出现的结点，要求时间复杂度尽可能高效

思想：使用辅助数组记录链表中以出现的数值，从而只需对链表进行一趟扫描

辅助数组 q 大小为 n + 1，初始值为 0，依次扫描链表中各点并检查 q[|data|] 的值，为 0 就置 1 并保留该结点，为 1 就删去

重新排列链表

问题：有链表 $L = (a_{1}, \dots, a_{n})$ 现要排列成 $L^{^{'}} = (a_{1}, a_{n}, a_{2}, a_{n - 1}, \dots)$ ，要求空间复杂度 O(1)

思想：将后半部分逆置，然后从两端单链表依次取一个结点，按要求重排

取中间结点可以取两个指针，一个一次走一步，一个一次走两步

思想拓展

一个长度为 N 的整形数组 A[1...N]，给定整数 X，请设计一个时间复杂度不超过 $O (n \log_{2} n)$ 的算法，查找出这个数组中所有两两之和等于 X 的整数对

实现这个有两种方法：

使用时间复杂度为 $O (n \log_{2} n)$ 排序成有序数组，然后分别从数据的小端 i = 1 和大端 j = N 开始查找，若 A[i] + A[j] < X，i++；若 A[i] + A[j] > X，j--；如果相等就输出并 i++, j--；当 i > j 时停止，总复杂度 $O (n \log_{2} n)$
使用 HashSet，迭代数组若 set.contains(X - A[i]) 则输出，否则将 A[i] 放入 HashSet 中，时间复杂度是 O(n)

java


// 第一种方法

public static void expectSumBySort(int[] arr, int expectSum)

{

    if(arr == null || arr.length == 0)

        return;

    Arrays.sort(arr);

    int left = 0, right = arr.length - 1;



    while(left < right)

    {

        if(arr[left] + arr[right] > expectSum)

            right--;

        else if(arr[left] + arr[right] < expectSum)

            left++;

        else//equal

        {

            System.out.println(arr[left] + " + " + arr[right] + " = " + expectSum); 

            left++;

            right--;

        }

    }

}



// 第二种方法

public static void expectSumBySet(int[] arr, int expectSum)

{

    if(arr == null || arr.length == 0)

        return;

    HashSet<Integer> intSets = new HashSet<Integer>(arr.length);



    int suplement;

    for (int i : arr)

    {

        suplement = expectSum - i;

        if(!intSets.contains(suplement)){

            intSets.add(i);

        }else{

            System.out.println(i + " + " + suplement + " = " + expectSum);

        }

    }

}

线性表的定义和基本操作 ​