2367. 算術三元組的數(shù)目

解法一：三指針

按照題意，依次枚舉三元組中的每一個元素即可。

Python版本

C++版本

復雜度分析

• 時間復雜度：O(N ^ 3). ?n 指的是數(shù)組 nums 的長度。第一次循環(huán)遍歷整個數(shù)組，其后兩次遍歷分別間隔一位，復雜度應為 n * (n - 1) * (n - 2)，省去系數(shù)；

• 空間復雜度：O(1). 數(shù)組中并未使用額外的數(shù)組空間存儲。

解法二：雙指針 + 數(shù)組

分兩次搜索滿足兩個表達式的結果。

第一次搜索滿足第一個表達式的下標組合，暫存于 mid 數(shù)組中；

由于兩個表達式差值相等，從集合的角度看，第二次搜索滿足第二個表達式的下標組合，一定在上次搜索的結果中；因此第二次搜索 mid 數(shù)組，統(tǒng)計 nums[j]重合的次數(shù)即可；

Python 版本

C++版本

復雜度分析

• 時間復雜度：O(N ^ 2). 此處 n 指的是 nums 數(shù)組的長度。第二重循環(huán)在第一重的基礎上偏移一個單位，復雜度為 n * (n - 1), 省略系數(shù)；

• 空間復雜度：O(N ^ 2). 此處 n 指的是 nums 數(shù)組的長度。兩個下標構成組合，總計為 n * (n - 1) / 2， 省略系數(shù)。

證明

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

2. 搜索整個 nums 數(shù)組的目的是找到三個元素，從后向前，兩兩元素的差值為diff的組合；

3. 由于diff最大值為50，nums數(shù)組嚴格遞增，且值域為[1, 200]，那么必然存在 nums[j] - nums[i] == diff的多個組合；

4. 第一次尋找nums[j] - nums[i],遍歷整個數(shù)組，用數(shù)組存儲滿足nums[j] - nums[i] == diff的所有下標組合；

5. 其中nums[j]會被重用，它同時存在于 nums[j] - nums[i] == diff和 ?nums[k] - nums[j] == diff 兩個關系式中；

6. 第一次遍歷整個數(shù)組 nums尋找diff的組合，必然包含第二次遍歷 nums[k] - nums[j] == diff的組合。

解法三：枚舉 + 集合

只需枚舉三元組中位序最大的元素，判斷其余兩個元素是否在數(shù)組當中即可。

Python 版本

C++版本

復雜度分析

• 時間復雜度：O(N ^ 2). 這里的 n 指的是 nums 數(shù)組的長度， 成員判斷需遍歷整個nums數(shù)組兩次，復雜度為 n ?* (2 * n)。

• 空間復雜度: O(1). 數(shù)組中并未使用額外的空間。

證明

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

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

由 ① + ②可得③：nums[k] - nums[i] == 2 * diff。由 ③， ②兩式聯(lián)列并變形可得：④nums[k] - 2 * diff == nums[i]； ⑤nums[k] - diff = nums[j]。由于題目中已經(jīng)給出 diff，因此可以直接枚舉nums[k]，同時驗證nums[i], nums[j]的存在性即可；

鳴謝