leetcode 532题

leetcode 532 数组中的 k-diff 数对

给你一个整数数组 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) 。

思路

先循环遍历数组里面每个数字的出现次数，把它放置到一个 map 中；然后遍历这个 map，这时有两种情况，如果 k 是 0 时，只要 key 对应的值大于 1，count 就加 1，第二种情况 k > 0，这个时候需要判断 map[key + k] 是否大于 1，这也需要 count + 1，遍历结束，便可以得到结果。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function findPairs(nums, k) {
    if (k === 0 && nums.length === 0) {
        return 0;
    }

    const map = {};
    for (const num of nums) {
        map[num] = map[num] ? map[num] + 1 : 1;
    }

    let count = 0;
    for (const key in map) {
        if (k === 0 && map[key] > 1) {
            count++;
        }
        if (k > 0 && map[+key + k] > 0) {
            count++;
        }
    }

    return count;
}

复杂度分析:

时间复杂度: O(N)
空间复杂度：O(N)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python

leetcode 532 数组中的 k-diff 数对

思路

代码

CATALOG

FEATURED TAGS

FRIENDS