【算法练习】85.差的绝对值为 K 的数对数目——计数

⭐加入组队刷题，抱团生长，每天进步⭐

可暴力，也可计数。

——leetcode此题热评

哈喽，大家好，我是一条。

糊涂算法，难得糊涂

点击《糊涂算法》系统学习

难度：简单

给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。

|x| 的值定义为：

• 如果 x >= 0 ，那么值为 x 。
• 如果 x < 0 ，那么值为 -x 。

示例 1：

输入：nums = [1,2,2,1], k = 1
输出：4
解释：差的绝对值为 1 的数对为：
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]
- [1,2,2,1]

示例 2：

输入：nums = [1,3], k = 3
输出：0
解释：没有任何数对差的绝对值为 3 。

示例 3：

输入：nums = [3,2,1,5,4], k = 2
输出：3
解释：差的绝对值为 2 的数对为：
- [3,2,1,5,4]
- [3,2,1,5,4]
- [3,2,1,5,4]

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100
• 1 <= k <= 99

首先暴力枚举是肯定可以实现的，但是如何把时间复杂度提升到O(n)

采用计数的思想。

• 因为题目给了范围，我们可以用一个长度为101的数组。
• 数的值对应下标的位置，如果该位置有值，置为1。没有值就是0。
• 依次将相隔为k的两个值相乘，如果为1，说明是1*1,即两个位置都有值，找到一组解。
• 统计解的个数

所有leetcode代码已同步至github

欢迎star

class Solution {
    public int countKDifference(int[] nums, int k) {
        int[] cnt=new int[101];
        for(int i=0;i 
Result 
 
 
复杂度分析
 
 
时间复杂度：O(N)
 
 
 
粉丝福利 
 
 
⭐今天是坚持刷题更文的第85/100天
 
 
⭐各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力
 
 
⭐更多数据结构和算法讲解欢迎关注专栏《糊涂算法》
 
 
为了回馈各位粉丝，礼尚往来，给大家准备了一些学习资料
 
 

  点击下方卡片
 关注后回复
 算法 领取