泰州公司做网站,好看大方的企业网站源码.net,山东网站备案时间,网站建设合同解除函2824. 统计和小于目标的下标对数目 2824. 统计和小于目标的下标对数目 一、题目描述二、我的想法 一、题目描述
给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target #xff0c;请你返回满足 0 i j n 且 nums[i] nums[j] target 的下标对…2824. 统计和小于目标的下标对数目 2824. 统计和小于目标的下标对数目 一、题目描述二、我的想法 一、题目描述
给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target 请你返回满足 0 i j n 且 nums[i] nums[j] target 的下标对 (i, j) 的数目。
示例 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 提示
1 nums.length n 50-50 nums[i], target 50
二、我的想法
与两数之和类似。
可以将数组先排个序因为只要求返回最后的数量而不是具体的下标。使用双指针一个 left 指向最开始的位置一个 right 指向末尾。再加上一个变量 count 用来记录数量。使用循环。因为数组被排序排好了 1如果 left 指针指向的元素加上 right 指向的元素和大于等于 target那说明最大的数太大了往左移看看有没有小一点的能满足条件的数 2如果 left 指针指向的元素加上 right 指向的元素和小于 target满足条件那说明 right 左边的数加上 left 指向的元素的和全都小于 target count 加上 right - left把这些全都加上left 就可以向右移了。等 left 大于等于 right 的时候就可以结束循环最后返回 count 作为结果。
class Solution:def countPairs(self, nums: List[int], target: int) - int:nums.sort()numsLen len(nums)left 0right numsLen - 1count 0while left right:if nums[left] nums[right] target:right - 1else:count right - leftleft 1return count
