代码编织梦想

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

给你一个整数数组 nums 和一个整数 k,请你在数组中找出 不同的 k-diff 数对,并返回不同的 k-diff 数对 的数目。

k-diff 数对定义为一个整数对 (nums[i], nums[j]) ,并满足下述全部条件:

0 <= i, j < nums.length
i != j
nums[i] - nums[j] == k
注意,|val| 表示 val 的绝对值。

示例 1:

输入:nums = [3, 1, 4, 1, 5], k = 2
输出:2
解释:数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
尽管数组中有两个 1 ,但我们只应返回不同的数对的数量。
示例 2:

输入:nums = [1, 2, 3, 4, 5], k = 1
输出:4
解释:数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5) 。
示例 3:

输入:nums = [1, 3, 1, 5, 4], k = 0
输出:1
解释:数组中只有一个 0-diff 数对,(1, 1) 。
 

提示:

1 <= nums.length <= 104
-107 <= nums[i] <= 107
0 <= k <= 107

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/k-diff-pairs-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

* 解题思路:
* 使用动态区间的概念,首先对数组进行排序。
* 然后规划一个区间[left,right]
* 如果right-left>k,那么left向右移动找到不等于当前值的数。
* 如果right-left<k,那么right向右移动找到不等于当前值的数。
* 如果right-left=k,那么left向右移动,记录num++。
* 如果key==0,则记录重复的数的个数即可。

代码:

public class Solution532 {

    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);

        //如果k==0,则计算重复的即可
        int num = 0;
        if (k == 0) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            }
            for (int key : map.keySet()) {
                if (map.get(key) > 1) {
                    num++;
                }
            }
            return num;
        }

        int left = 0;
        int right = 1;

        while (left >= 0 && right >= 0) {
            int leftValue = nums[left];
            int rightValue = nums[right];
            int diff = rightValue - leftValue;
            if (diff < k) {
                right = findNext(nums, right);
            } else if (diff > k) {
                left = findNext(nums, left);
            } else {
                num++;
                left = findNext(nums, left);
            }
        }
        return num;
    }

    private int findNext(int[] nums, int index) {
        int value = nums[index];
        int nextValue = nums[index];
        while (value == nextValue) {
            if (++index == nums.length) {
                return -1;
            }
            nextValue = nums[index];
        }
        return index;
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/rzleilei/article/details/125330151

leetcode中的那些题_每天开心成为别人的望尘莫及的博客-爱代码爱编程_if (!state.id_map.containskey(id))

目录 1. 两数之和 2. 两数相加 3. 无重复字符的最长子串 *******4.寻找两个有序数组的中位数(官方解答) : 5.最长回文子串(官方解答) 15. 三数之和 16. 最接近的三数之和 17.电话号码的字母组合 解题 18.四数之和 19.删除链表的倒数第N个节点(官方解答) 20.有效的括号(官方解答) 21. 合

Leetcode-How-What 力扣Leetcode刷题指南-爱代码爱编程

Leetcode-How-What 力扣Leetcode刷题指南 About the way how to use Leetcode wisely for preparing the interview and the solutions to some Leetcode problems’. 怎样为准备面试机智聪明的刷题(高效刷题)以及一些题目的题解。

力扣博文链接-爱代码爱编程

目录 树 堆 模拟 枚举 组合 链表 递归 宽搜 指针 进制 图论 分析 贪心 数学 构造 概率 排序 日期 KMP RMQ Trie树 对顶堆 扫描线 自动机 格雷码 字符串 思维题 逆序对 回文串 全排列 离散化 线段树 平衡树 单调栈 找规律 博弈论 并查集 前缀和 快速幂

字节跳动的算法面试题是什么难度?(第二弹)-爱代码爱编程

点击蓝色“力扣加加”关注我哟 加个“星标”,带你揭开算法的神秘面纱! ❝ 这是力扣加加第「19」篇原创文章 ❞ 字节跳动的算法面试题是什么难度?(第二弹) 第一弹地址:字节跳动的算法面试题是什么难度? 由于 lucifer 我是一个小前端, 最近也在准备写一个《前端如何搞定算法面试》的专栏,因此最近没少看各大公司的面试

Leetcode---动规问题汇总-爱代码爱编程

Leetcode 题解 - 动态规划 斐波那契数列 1. 爬楼梯2. 强盗抢劫3. 强盗在环形街区抢劫4. 信件错排5. 母牛生产矩阵路径 1. 矩阵的最小路径和2. 矩阵的总路径数数组区间 1. 数组区间和2. 数组中等差递增子区间的个数分割整数 1. 分割整数的最大乘积2. 按平方数来分割整数3. 分割整数

力扣编程题-解法汇总-爱代码爱编程

一.力扣链接: 题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台 备注:以后每个工作日从前往后刷一道题,然后再加一道每日新题。每天两道题。 二.目录 力扣解法汇总1- 两数之和_分享+记录-CSDN博客 力扣解法汇总2-两数相加_分享+记录-CSDN博客 力扣解法汇总3-无重复字符的最长子串_分享+记录-CSDN博客 力扣

面试题--算法零散汇总(更多更系统数据结构与算法知识见本栏目数据结构与算法)-爱代码爱编程

1.闲聊力扣算法第一题 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 示例 1: 输入:nums = [2,7,11,15], target =

【leetcode】167-两数之和ii -输入有序数组_酥酥~的博客-爱代码爱编程

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。 以长度为 2

877 · 同和分割数组_yinhua405的博客-爱代码爱编程

给定一个有n个整数的数组,判断是否存在满足以下条件的三元组 (i, j, k): 0 < i, i + 1 < j, j + 1 < k < n - 1子数组 (0, i - 1), (i + 1, j - 1), (j + 1, k - 1)和(k + 1, n - 1) 的和相等。定义子数组(L, R)表示原始数组从元素下

力扣之螺旋矩阵_c-v御用工程师的博客-爱代码爱编程

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 示例 1: 输入:matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出:[1,2,3,6,9,8,7,4,5] 分析:本题力扣所给标签是中等题,但是其实本题除了几个需要注意的点外,整体难度也就是简单题。现在我们来分析一下,他给你一个m行

算法练习-链表 leetcode 160. 相交链表_yinyl03的博客-爱代码爱编程

今日心情:🥱🥱 题目描述: LeetCode 160. 相交链表 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交:   题目数据 保证 整个链式结构中不存在环。 注意,函数返回结果后,链表

k 次取反后最大化的数组和_me!的博客-爱代码爱编程

K 次取反后最大化的数组和 给你一个整数数组 nums 和一个整数 k ,按以下方法修改该数组: 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。 以这种方式修改数组后,返回数组 可能的最大和 。 示例 1: 输入:nums = [4,2,3], k = 1 输出:5

入门力扣自学笔记64 c++ (题目编号532)_dk_sorhic的博客-爱代码爱编程

532. 数组中的 k-diff 数对 题目: 给你一个整数数组 nums 和一个整数 k,请你在数组中找出 不同的 k-diff 数对,并返回不同的 k-diff 数对 的数目。 k-diff 数对定义为一个整数对 (nums[i], nums[j]) ,并满足下述全部条件: 0 <= i, j < nums.length i !=

本地leetcode运行和调试环境部署_hellowild的博客-爱代码爱编程

本地Leetcode运行和调试环境部署 工具及要求 vscodeg+±10(能够使用#include<bits/stdc++.h>)能够在vscode将c++代码跑起来熟悉Linux命令实施步骤 其实一共是三个文件: main.cpp :主体代码input.txt : 模拟输入内容output.txt : 模拟输出内容main.cpp内

分治(归并排序、汉罗塔问题)_分治排序是什么-爱代码爱编程

文章目录 归并排序汉诺塔问题添加括号的所有方式分析代码 至少有 K 个重复字符的最长子串 归并排序 归并排序是典型的分治思想 void sort(int[] nums, int lo, in

关于“labuladong的算法小抄”的学习笔记-爱代码爱编程

目录 作者给自己的话一、学习算法和刷题的框架思维1、数据结构的存储方式2、数据结构的基本操作3、算法刷题指南 二、labuladong的刷题心得1、算法的本质2、数组/单链表系列算法3、二叉树系列算法