Category: 数据结构

在数据结构中维护前缀和:区间(矩形/路径)和等于(大于)目标值

摘要: 区间和等于目标值的各种变种问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 【模板】前缀和与差分 中我们了解了一维和二维前缀和的算法原理和代码模板。在实际问题中我们经常要将前缀和维

二维偏序问题:扫描线+树状数组

摘要: 一个维度用扫描线(排序)保证有序;一个维度用树状数组保证有序;维护权值的最值 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 二维偏序问题形式化定义如果形式化地定义,二维偏序问题的描述如下。

离线分治:基于时间 (CDQ分治)

摘要: 基于时间的离线分治,逆序对个数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 很多数据结构的问题可以抽象为“维护一系列数据,并对一系列操作一次做出响应”,这些操作可以分为两种: 查询型操作

归并树:区间大于x的元素个数

摘要: 归并树,区间大于 x 的元素个数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们从 315. 计算右侧小于当前元素的个数 出发,引出一个维护区间大于 x 的元素个数的数据结构:归并树

划分树:区间第k大

摘要: 划分树,区间第 k 大数 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们从 力扣315-索引数组,归并树 出发,引出一个维护区间第 k 大数的数据结构:划分树。 对于区间 $[i,

分块查找表:区间修改,区间最值查询

摘要: 分块查找表,原理与实现,解决带修改的区间最值查询问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 分块查找表的主要思路是对于数据数组 nums[0..n-1], 共 n 个元素,每 $\s

Range模块:维护区间的增删改查

摘要: 基于平衡树的Range模块,维护区间的增删改查 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们通过力扣 715 来看一下可以动态维护区间的增删改查的组件的功能与实现,本题的代码可以作

前驱后继与线索二叉树

摘要: 线索树 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 对树进行遍历的过程中,会产生一个遍历序,参考文章 遍历序的基本概念与性质。基于这个遍历序,每个节点都有一个前驱节点与后继节点。 在实际问

参考字符串哈希定义数组哈希(数组的同构)

摘要: 类似于字符串哈希的数组哈希,以及在数组同构中的应用。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 字符串哈希 中我们学习了字符串哈希的原理与代码模板。 对于长度为 m 的字符串 s

Morris遍历与Morris序

摘要: 树的 Morris 遍历 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 树的前序、中序、后序遍历与DFS搜索 中,我们知道树的前序、中序和后序遍历都有递归和非递归算法。两者的额外空间

用哈希表和和双向链表的代码模板实现LFU

摘要: 实现 LFU 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 LRU:维护最近访问/插入的元素 中,我们基于 C++ STL 以及 Python OrderedDict 实现了 LRU

用哈希表和和双向链表的代码模板实现LRU

摘要: 实现LRU 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 LRU:维护最近访问/插入的元素 中,我们基于 C++ STL 以及 Python OrderedDict 实现了 LRU

二维树状数组:单点修改,矩阵和查询

摘要: 二维树状数组,单点修改与矩阵查询,原理与实现 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文通以 308. 二维区域和检索 - 可变 作为模板题来看一下二维树状数组的原理与实现。 本文的

【leetbook】树的技巧

摘要: 普通树的 Leetbook 目录,附链接 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings LeetBook 链接:树的技巧。 树的基本概念 树 根 树叶 兄弟 祖父 孙子 路径 路

【leetbook】哈希的技巧

摘要: 哈希技巧的 Leetbook 目录,附链接 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings LeetBook 链接:哈希思想。 哈希表基础知识 线性探测 945 闭散列表 邻接

手撕平衡树-Treap

摘要: Treap 的原理、代码模板、例题 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 此前,我们已经写过不少关于树的文章,包括二叉树、二叉查找树、平衡树。 二叉树 树的DFS

手撕平衡树-数组模拟链表实现二叉查找树

摘要: 用数组模拟链表的方式实现二叉查找树 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们用数组模拟链表的方式实现二叉查找树,并形成代码模板。 关于二叉查找树,在文章 手撕

用数组模拟链表的方式实现【带权有向图的邻接表】

摘要: 数组模拟链表的方式实现图的邻接表,代码模板 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 邻接表 中,我们学习了邻接表及其应用,在文章 用数组模拟双向循环链表 中,

结合链表容易删除的特点使用逆向思维

摘要: 链表易于删除节点,方便维护逆向思维 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 逆向思维是一种常见的算法思维方式,在文章 逆向思维 中,我们例举了不少 leetcode 上用逆向思维解决的

用数组模拟双向循环链表

摘要: 用数组模拟双向循环链表 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 【模板】双向链表 中,我们实现了双向循环链表,并将其用在实现了 LFU,以及实现循环双端队列中

大学数据结构笔记

摘要: 大学数据结构的笔记 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 大学数据结构笔记,2017年,共 51 页。主要内容如下: 数据结构基础 栈 队列 表 静态查找表 高级

leetcode题目汇总-栈

摘要: 力扣上的栈的问题汇总 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文总结一下力扣上 2000 题以内的关于栈的 73 道题。 栈是一种最基础的数据结构,本身是比较简单的,而且没什么变化

两本高级数据结构的英文书

摘要: 两本高级数据结构书 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文给大家分想两本高级数据结构的书。LeetCode 主要是针对面试的算法刷题平台,在 LeetCode

中序遍历过程中通过引用维护前驱

摘要: 中序遍历,通过引用维护前驱 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 中序遍历是二叉搜索树的重要操作,相关的问题很多,参考文章 二叉查找树的中序遍历和前驱后继。 有时在中序遍历过程中需要

二叉树的建树

摘要: 本文介绍了一类由给定的递归定义的建树规则进行建树的问题。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 相关的内容: 递归 中缀表达式建表达式树 后缀表达式建表达式树 抽象问题给出一组

OrderedDict:维护插入顺序的有序字典

摘要: 维护插入顺序的有序字典 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 LRU:维护最近访问/插入的元素 和 LFU:维护最频繁访问的元素 中,我们分别以模板题介绍了 LRU 和 LF

【模板】双向链表的懒释放

摘要: 双向链表的懒释放 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 惰性更新与懒释放惰性更新是一种面对频繁操作时,先把操作记下来,等查询时再把记下的操作一次性都做掉,这在

【模板】双向链表

摘要: 双向循环链表的实现 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们实现双向循环链表的代码模板。并用改模板解决 641. 设计循环双端队列。 $1. 双向循环链表

【模板】无重哈希映射

摘要: 开散列表与闭散列表的哈希映射,代码模板 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 哈希映射是将哈希集合中的每个节点加一个数据的字段,其余部分与哈希集合基本一样。支持集合

用下标索引堆优化邻接表的 Prim 算法

摘要: 下标索引堆的应用。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们以 1135. 最低成本联通所有城市 来看一下如何用下标索引堆对邻接表的 Prim 算法进行优化。邻接表 + 二叉堆

【模板】哈希集合

摘要: 开散列表与闭散列表的哈希集合,代码模板 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们实现哈希集合的代码模板,开散列和闭散列两种处理冲突的方式均有实现。 之后再 7

哈希索引堆的索引优化

摘要: 哈希索引堆的优化 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 背景:哈希索引堆一般的堆不支持按key操作,例如按 key 删除,按 key 修改。 现实中这种需求是

哈希索引堆

摘要: 哈希索引堆,思想,代码模板,例子 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在常规的堆中,我们只能通过堆头访问堆中的最值元素,无法通过类似下标的方式访问堆中的其它元素。

全O(1)的数据结构:哈希表计数,支持查询计数最大与最小的键

摘要: 基于链表+哈希表解决与频数相关的设计问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 各位好,本文我们来看一个设计问题。在文章 设计-功能系统 中我们系统梳理过设计功能系统的问题。本文解决

邻接表

摘要: 邻接表的应用:桶、开散列表、树和图的存储 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们总结一下邻接表的各种应用。包括桶、开散列表、树和图的存储。 $0 邻接表邻接表可以看成带有索引

链表维护多项式的加法

摘要: 链表维护多项式加法,力扣 1634 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 链表的一种应用是维护多项式,本文我们通过一个题目看一下如何用链表进行多项式的存储,以及两个多项式链表如何求和

深拷贝

摘要: 经典的二叉堆的实现,附代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 今天我们看4个题,leetcode第1490题【1490. 克隆 N 叉树】,第133题【133. 克隆图

下标索引堆

摘要: 下标索引堆,思想,代码模板,例子 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 背景(1) 支持按 key 删除的堆一般的堆不支持按key操作,例如按 key 删除,

堆的标记删除

摘要: 带标记删除的堆 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们借鉴 GC 中的标记删除算法,在堆的元素中加上标记删除,实现对堆中元素的动态删除。 我们给出代码模板,最后用 239.

加索引的数组

摘要: 加索引的数组 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 背景有些数据结构可以根据 key 快速找到其所在节点,例如哈希表、平衡树、Trie,跳表。这些可以看成是一

线性索引表

摘要: 线性索引表的原理,例子 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 线性索引表将数组中数据的 key 和数据在数组中的节点位置以元组的形式放进数组维护,这个保存 key 和节点位置的

对顶堆

摘要: 对顶堆的思想,在中位数问题中的应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 二叉堆 中,我们详细学习了二叉堆的原理、代码模板,以及在排序中的应用。 对于一些中位数问题,我们可以

二叉堆

摘要: 经典的二叉堆的实现,附代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文我们串讲一下经典的二叉堆的原理、实现,代码模板和应用。 $1 二叉堆原理堆是一种支持插入key,删除

对顶栈

摘要: 对顶栈的使用场景 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $1 场景有一个光标,给出对光标的操作序列,维护操作结果,当操作有以下特性时,对顶栈可以很好地解决。 一次只移动一位 添加、

加索引的链表

摘要: 加索引的链表 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:潮汐朝夕我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 背景有些数据结构可以根据 key 快速找到其所在节点,例如哈希表、平衡树、Trie,跳表。这些可以看成是一

随机队列

摘要: 本文介绍随机队列的原理和代码模板,以及 2 道 leetcode 相关题目。 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 随机队列 增加删 key 的支持 380. 常数时间插入、删除和

线段树大模板:区间修改(加法、乘法)、区间和查询

摘要: 线段树区间修改(加法、乘法)、区间和查询 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 线段树和树状数组:单点修改、区间和查询 中我们学习了线段树的单点更新、区间查询,并解决了区间求

单调队列

摘要: 单调队列的算法原理,代码模板和应用 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 本文详细介绍单调队列的算法原理、代码模板和应用。涉及到的题目汇总如下: 基本模型 239. 滑动窗口最大值

跳表

摘要: 跳表的设计与实现 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings $0 跳表背景与哈希表、平衡树、Trie类似,跳表也可以看成是一种自带索引的数据结构(索引结构)。即根据给定的 key,可以快

线段树:区间修改(更改为定值)、区间最值查询

摘要: 线段树,区间修改与区间查询,原理与实现,RMQ 问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的github:FennelDumplings我的leetcode:FennelDumplings 在文章 线段树和树状数组:单点修改、区间查询,区间求和问题 中,我们学习了带单点修改、区间