与众不同的网站,提供有经验的网站建设,如何生成短链接,旅游小程序页面设计模板统计和小于目标的下表对数目 题目及要求暴力枚举双指针在main内使用 题目及要求
给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target #xff0c;请你返回满足 0 i j n 且 nums[i] nums[j] target 的下标对 (i, j) 的数目。
示例 1请你返回满足 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
暴力枚举
思路定义ans用于记录数对双循环逐个去查找如果和小于目标则累加ans
class Solution {
public:int countPairs(vectorint nums, int target) {int nnums.size();int ans0;for(int i0;in;i){for(int ji1;jn;j){if(nums[i]nums[j]target)ans;}}return ans;}
};双指针
思路先排序然后定义两个指针分别指向头和尾如果当前数字小于目标值则代表右指针到左指针之间的数字对都满足条件全部加到ans内最后不断移动指针完成遍历最后返回ans
class Solution {
public:int countPairs(vectorint nums, int target) {sort(nums.begin(), nums.end()); // 对数组进行排序int n nums.size(); // 数组的大小int ans 0; // 记录满足条件的数字对数量int i 0, j n - 1; // 定义两个指针i指向开头j指向末尾while (i j) { // 当左指针小于右指针时进行循环if (nums[i] nums[j] target) { // 如果当前数字对之和大于等于目标值j--; // 右指针向左移动一位} else { // 如果当前数字对之和小于目标值ans j - i; // 将右指针和左指针之间的数字对数量累加到答案中i; // 左指针向右移动一位}}return ans; // 返回满足条件的数字对数量}
};
在main内使用
int main() {vectorint nums {1, 3, 4, 6, 8};int target 7;int ans 0;sort(nums.begin(), nums.end());ans countPairs(nums, target);cout 数字对之和至少为 target 的数量为: ans endl;return 0;
}
