题目描述
这是 LeetCode 上的 611. 有效三角形的个数 ,难度为 中等。
Tag : 「排序」、「二分」、「双指针」
给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3 复制代码
注意:
- 数组长度不超过1000。
- 数组里整数的范围为 [0, 1000]。
基本分析
根据题意,是要我们统计所有符合 nums[k] + nums[j] > nums[i]nums[k]+nums[j]>nums[i] 条件的三元组 (k,j,i)(k,j,i) 的个数。
为了防止统计重复的三元组,我们可以先对数组进行排序,然后采取「先枚举较大数;在下标不超过较大数下标范围内,找次大数;在下标不超过次大数下标范围内,找较小数」的策略。
排序 + 暴力枚举
根据「基本分析」,我们可以很容易写出「排序 + 三层循环」的实现。
代码:
class Solution { public int triangleNumber(int[] nums) { int n = nums.length; Arrays.sort(nums); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i - 1; j >= 0; j--) { for (int k = j - 1; k >= 0; k--) { if (nums[j] + nums[k] > nums[i]) ans++; } } } return ans; } } 复制代码
- 时间复杂度:排序时间复杂度为 O(n\log{n})O(nlogn);三层遍历找所有三元祖的复杂度为 O(n^3)O(n3)。整体复杂度为 O(n^3)O(n3)
- 空间复杂度:O(\log{n})O(logn)
排序 + 二分
、
根据我们以前讲过的的 优化枚举的基本思路,要找符合条件的三元组,其中一个切入点可以是「枚举三元组中的两个值,然后优化找第三数的逻辑」。
我们发现,在数组有序的前提下,当枚举到较大数下标 ii 和次大数下标 jj 时,在 [0, j)[0,j) 范围内找的符合 nums[k'] + nums[j] > nums[i]nums[k′]+nums[j]>nums[i] 条件的 k'k′ 的集合时,以符合条件的最小下标 kk 为分割点的数轴上具有「二段性」。
令 kk 为符合条件的最小下标,那么在 nums[i]nums[i] 和 nums[j]nums[j] 固定时,[0,j)[0,j) 范围内:
- 下标大于等于 kk 的点集符合条件 nums[k'] + nums[j] > nums[i]nums[k′]+nums[j]>nums[i];
- 下标小于 kk 的点集合不符合条件 nums[k'] + nums[j] > nums[i]nums[k′]+nums[j]>nums[i]。
因此我们可以通过「二分」找到这个分割点 kk,在 [k,j)[k,j) 范围内即是固定 jj 和 ii 时,符合条件的 k'k′ 的个数。
代码:
class Solution { public int triangleNumber(int[] nums) { int n = nums.length; Arrays.sort(nums); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i - 1; j >= 0; j--) { int l = 0, r = j - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] + nums[j] > nums[i]) r = mid; else l = mid + 1; } if (l == r && nums[r] + nums[j] > nums[i]) ans += j - r; } } return ans; } } 复制代码
- 时间复杂度:排序时间复杂度为 O(n\log{n})O(nlogn);两层遍历加二分所有符合条件的三元组的复杂度为 O(n^2*\log{n})O(n2∗logn)。整体复杂度为 O(n^2*\log{n})O(n2∗logn)
- 空间复杂度:O(\log{n})O(logn)
排序 + 双指针
更进一步我们发现,当我们在枚举较大数下标 ii,并在 [0, i)[0,i) 范围内逐步减小下标(由于数组有序,也就是逐步减少值)找次大值下标 jj 时,符合条件的 k'k′ 必然是从 00 逐步递增(这是由三角不等式 nums[k] + nums[j] > nums[i]nums[k]+nums[j]>nums[i] 所决定的)。
因此,我们可以枚举较大数下标 ii 时,在 [0, i)[0,i) 范围内通过双指针,以逐步减少下标的方式枚举 jj,并在遇到不满足条件的 kk 时,增大 kk 下标。从而找到所有符合条件三元组的个数。
代码:
class Solution { public int triangleNumber(int[] nums) { int n = nums.length; Arrays.sort(nums); int ans = 0; for (int i = 0; i < n; i++) { for (int j = i - 1, k = 0; k < j; j--) { while (k < j && nums[k] + nums[j] <= nums[i]) k++; ans += j - k; } } return ans; } } 复制代码
- 时间复杂度:排序时间复杂度为 O(n\log{n})O(nlogn),双指针找所有符合条件的三元组的复杂度为 O(n^2)O(n2)。整体复杂度为 O(n^2)O(n2)
- 空间复杂度:O(\log{n})O(logn)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.611
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour… 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。