2367. 算术三元组的数目

解法一：三指针

按照题意，依次枚举三元组中的每一个元素即可。

Python版本

C++版本

复杂度分析

• 时间复杂度：O(N ^ 3).  n 指的是数组 nums 的长度。第一次循环遍历整个数组，其后两次遍历分别间隔一位，复杂度应为 n * (n - 1) * (n - 2)，省去系数；

• 空间复杂度：O(1). 数组中并未使用额外的数组空间存储。

解法二：双指针 + 数组

分两次搜索满足两个表达式的结果。

第一次搜索满足第一个表达式的下标组合，暂存于 mid 数组中；

由于两个表达式差值相等，从集合的角度看，第二次搜索满足第二个表达式的下标组合，一定在上次搜索的结果中；因此第二次搜索 mid 数组，统计 nums[j]重合的次数即可；

Python 版本

C++版本

复杂度分析

• 时间复杂度：O(N ^ 2). 此处 n 指的是 nums 数组的长度。第二重循环在第一重的基础上偏移一个单位，复杂度为 n * (n - 1), 省略系数；

• 空间复杂度：O(N ^ 2). 此处 n 指的是 nums 数组的长度。两个下标构成组合，总计为 n * (n - 1) / 2， 省略系数。

证明

1. 用集合中父子集合的概念，理解满足 nums[j] - nums[i] == diff 且 nums[k] - nums[j] == diff的解的集合；

2. 搜索整个 nums 数组的目的是找到三个元素，从后向前，两两元素的差值为diff的组合；

3. 由于diff最大值为50，nums数组严格递增，且值域为[1, 200]，那么必然存在 nums[j] - nums[i] == diff的多个组合；

4. 第一次寻找nums[j] - nums[i],遍历整个数组，用数组存储满足nums[j] - nums[i] == diff的所有下标组合；

5. 其中nums[j]会被重用，它同时存在于 nums[j] - nums[i] == diff和  nums[k] - nums[j] == diff 两个关系式中；

6. 第一次遍历整个数组 nums寻找diff的组合，必然包含第二次遍历 nums[k] - nums[j] == diff的组合。

解法三：枚举 + 集合

只需枚举三元组中位序最大的元素，判断其余两个元素是否在数组当中即可。

Python 版本

C++版本

复杂度分析

• 时间复杂度：O(N ^ 2). 这里的 n 指的是 nums 数组的长度， 成员判断需遍历整个nums数组两次，复杂度为 n  * (2 * n)。

• 空间复杂度: O(1). 数组中并未使用额外的空间。

证明

①nums[j] - nums[i]  = diff

②nums[k] - nums[j] = diff

由 ① + ②可得③：nums[k] - nums[i] == 2 * diff。由 ③， ②两式联列并变形可得：④nums[k] - 2 * diff == nums[i]； ⑤nums[k] - diff = nums[j]。由于题目中已经给出 diff，因此可以直接枚举nums[k]，同时验证nums[i], nums[j]的存在性即可；

鸣谢