门户网站推广,免费软件定位对方手机位置,域名停域app免费下载,WordPress画表格题目描述 这是 LeetCode 上的 「2824. 统计和小于目标的下标对数目」 #xff0c;难度为 「简单」。 Tag : 「排序」、「二分」、「双指针」 给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target#xff0c;请你返回满足 0 i j n 且 nums[i] n… 题目描述 这是 LeetCode 上的 「2824. 统计和小于目标的下标对数目」 难度为 「简单」。 Tag : 「排序」、「二分」、「双指针」 给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target请你返回满足 0 i j n 且 nums[i] nums[j] target 的下标对 的数目。 示例 1 输入nums [-1,1,2,3,1], target 2输出3解释总共有 3 个下标对满足题目描述- (0, 1) 0 1 且 nums[0] nums[1] 0 target- (0, 2) 0 2 且 nums[0] nums[2] 1 target - (0, 4) 0 4 且 nums[0] nums[4] 0 target注意 (0, 3) 不计入答案因为 nums[0] nums[3] 不是严格小于 target 。 示例 2 输入nums [-6,2,5,-2,-7,-1,3], target -2输出10解释总共有 10 个下标对满足题目描述- (0, 1) 0 1 且 nums[0] nums[1] -4 target- (0, 3) 0 3 且 nums[0] nums[3] -8 target- (0, 4) 0 4 且 nums[0] nums[4] -13 target- (0, 5) 0 5 且 nums[0] nums[5] -7 target- (0, 6) 0 6 且 nums[0] nums[6] -3 target- (1, 4) 1 4 且 nums[1] nums[4] -5 target- (3, 4) 3 4 且 nums[3] nums[4] -9 target- (3, 5) 3 5 且 nums[3] nums[5] -3 target- (4, 5) 4 5 且 nums[4] nums[5] -8 target- (4, 6) 4 6 且 nums[4] nums[6] -4 target 提示 基本分析 为了方便先对 nums 进行排序。 当 nums 有了有序特性后剩下的便是「遍历右端点在右端点左侧找最大合法左端点」或「遍历左端点在左端点右侧找最大合法右端点」过程。 排序 二分 这是一种「遍历右端点在右端点左侧找最大合法左端点」做法。 遍历右端点 i然后在 范围内进行二分找到最大的满足 的位置 j。 若存在这样左端点 j说明以 为右端点时共有 个范围为 个合法左端点需要被统计。 Java 代码 class Solution { public int countPairs(ListInteger nums, int target) { Collections.sort(nums); int n nums.size(), ans 0; for (int i 1; i n; i) { int l 0, r i - 1; while (l r) { int mid l r 1 1; if (nums.get(mid) nums.get(i) target) l mid; else r mid - 1; } if (nums.get(r) nums.get(i) target) ans r 1; } return ans; }} C 代码 class Solution {public: int countPairs(vectorint nums, int target) { sort(nums.begin(), nums.end()); int n nums.size(), ans 0; for (int i 1; i n; i) { int l 0, r i - 1; while (l r) { int mid l r 1 1; if (nums[mid] nums[i] target) l mid; else r mid - 1; } if (nums[r] nums[i] target) ans r 1; } return ans; }}; Python 代码 class Solution: def countPairs(self, nums: List[int], target: int) - int: nums.sort() n, ans len(nums), 0 for i in range(1, n): l, r 0, i - 1 while l r: mid l r 1 1 if nums[mid] nums[i] target: l mid else: r mid - 1 if nums[r] nums[i] target: ans r 1 return ans TypeScript 代码 function countPairs(nums: number[], target: number): number { nums.sort((a,b)a-b); let n nums.length, ans 0; for (let i 1; i n; i) { let l 0, r i - 1; while (l r) { const mid l r 1 1; if (nums[mid] nums[i] target) l mid; else r mid - 1; } if (nums[r] nums[i] target) ans r 1; } return ans;}; 时间复杂度排序复杂度为 构造答案复杂度为 。整体复杂度为 空间复杂度 排序 双指针 这是一种「遍历左端点在左端点右侧找最大合法右端点」做法。 使用 l 和 r 分别指向排序好的 nums 的首尾。 若当前 说明此时对于 l 来说r 并不合法对 r 自减左移。 直到满足 此时对于 l 来说找到了最右侧的合法右端点 r在 期间的数必然仍满足 共有 个范围为 个合法右端点需要被统计。 Java 代码 class Solution { public int countPairs(ListInteger nums, int target) { Collections.sort(nums); int n nums.size(), ans 0; for (int l 0, r n - 1; l r; l) { while (r 0 nums.get(l) nums.get(r) target) r--; if (l r) ans r - l; } return ans; }} C 代码 class Solution {public: int countPairs(vectorint nums, int target) { sort(nums.begin(), nums.end()); int n nums.size(), ans 0; for (int l 0, r n - 1; l r; l) { while (r 0 nums[l] nums[r] target) r--; if (l r) ans r - l; } return ans; }}; Python 代码 class Solution: def countPairs(self, nums: List[int], target: int) - int: nums.sort() n, ans len(nums), 0 l, r 0, n - 1 while l r: while r 0 and nums[l] nums[r] target: r - 1 if l r: ans r - l l 1 return ans TypeScript 代码 function countPairs(nums: number[], target: number): number { nums.sort((a,b)a-b); let n nums.length, ans 0; for (let l 0, r n - 1; l r; l) { while (r 0 nums[l] nums[r] target) r--; if (l r) ans r - l; } return ans;}; 时间复杂度排序复杂度为 构造答案复杂度为 。整体复杂度为 空间复杂度 最后 这是我们「刷穿 LeetCode」系列文章的第 No.2824 篇系列开始于 2021/01/01截止于起始日 LeetCode 上共有 1916 道题目部分是有锁题我们将先把所有不带锁的题目刷完。 在这个系列文章里面除了讲解解题思路以外还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。 为了方便各位同学能够电脑上进行调试和提交代码我建立了相关的仓库https://github.com/SharingSource/LogicStack-LeetCode 。 在仓库地址里你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地
