线性表的定义和基本操作

线性表的定义

线性表是具有相同数据类型 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);  // 销毁操作，回收线性表的内存

线性表的顺序表示

顺序表的定义

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

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

注意：线性表中元素的位序是从 1 开始的，而数组中元素的下标是从 0 开始的

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

#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++ 的内存分配

顺序表的特点：

顺序表最主要的特点是随机访问，给了首地址和元素序号可在 O(1) 内找到元素
顺序表的存储密度高，每个结点只存储数据元素
顺序表逻辑及上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素

顺序表上基本操作的实现

插入操作

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;
}

最好情况：表尾插入，元素后移不执行，时间复杂度为 O(1)

最坏情况：表头插入，元素后移执行 n 次，时间复杂度为 O(n)

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

删除操作

bool ListDelete(SqList &L, int i, ElemType &e){
    if (i < 1 || i > L.length)  // 验证 i 是否越界
        return false;
    e = L.data[i - 1];  // 将要删除的元素赋值给 e
    for (int j = i; j < L.length; j++)  // 将第 i 位置后的元素前移
        L.data[j - 1] = L.data[j];
    L.length--;  // 长度减一
    return true;
}

最好情况：删除表尾元素，无需移动元素，时间复杂度为 O(1)

最坏情况：删除表头元素，需移动表头外的元素，时间复杂度为 O(n)

平均情况：计算法和插入时一样，时间复杂度为 O(n)

按值查找

int LocateElem(SqList L, ElemType e){
    int i;
    for (i = 0; i < L.length; i++)
        if (L.data[i] == e)
            return i + 1;  // 返回其位序 i + 1
    return 0;  // 查找失败
}

最好情况：查找元素在表头，仅比较一次，时间复杂度为 O(1)

最坏情况：查找元素在表尾，需要比较 n 次，时间复杂度为 O(n)

平均情况：计算法和插入时一样，时间复杂度为 O(n)

综合应用题

删除表内所有为 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;
}

若有 *p 要把 *s 插入 *p 的前面，这时我们可以把 *s 插入 *p 的后面，然后互换数据

// 把 s 插入 p 后面
s -> next = p -> next;
p -> next = s;
// 交换数据
temp = p -> data;
p -> data = s -> data;
s -> data = temp;

删除结点操作

删除结点，首先拿到它的前驱，然后检查结点的合法性，然后删除，时间复杂度是 O(n)

bool ListDelete(LinkList L, int i){
	LinkList p = GetElem(L, i - 1);  // 拿到前驱
	if(NULL == p) {  // 验证合法性
		return false;
	}
    // 删除数据
	LinkList q;
	q = p -> next;
    if (q == NULL) return false;
	p -> next = q -> next;
    free(q);
	return true;
}

若有 *p 且要把 *p 删除，我们可以把 *p 的数据域等于它的下个结点，然后把下个结点删除

q = p -> next;
p -> data = q -> data;  // 等于下个结点的数据域
p -> next = q -> next;  // 删除下个结点
free(q);

求表长操作

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

当访问到空结点的时候计数就是表的长度，时间复杂度是 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)，因为要拿到尾结点的前驱

循环双链表

循环双链表与循环单链表不同的是，除了尾结点的 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. 链式存储就只需要在使用时分配，操作灵活、高效

取舍顺序表和链表

基于存储的考虑：难以估计线性表长度或规模时，使用链表；但链表存储密度低，能估计规模时用顺序表
基于运算的考虑：需要大量按序号访问操作时，使用顺序表；需要大量插入删除时，使用链表
基于环境的考虑：所有语言都有数组，但不是所有语言都有指针，相对来讲顺序表更好实现

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

综合应用题

递归删除链表中值为 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);
        }
    }
}

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