[LintCode] K-diff Pairs in an Array

Leck1e 发布于2019-08-15 18:16 / 1199人阅读

Problem

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example

Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Solution

public class Solution {
    /**
     * @param nums: an array of integers
     * @param k: an integer
     * @return: the number of unique k-diff pairs
     */
    public int findPairs(int[] nums, int k) {
        //it actually wants unique pairs, so need to sort and leave out the duplicates
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length-1; i++) {
            if (i != 0 && nums[i] == nums[i-1]) continue;
            for (int j = i+1; j < nums.length; j++) {
                if (j != i+1 && nums[j] == nums[j-1]) continue;
                if (nums[j] - nums[i] == k) count++;
            }
        }
        return count;
    }
}

GPU云服务器云服务器 in_array() in_array in_array()函数 in_array()示例代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69719.html

leetcoed 532 K-diff Pairs in an Array

摘要：由于无法处理相同的操作，所依对于的时候，我采用了进行操作。为时，对于每一次遍历，找到这个值是否已经存在在里，同时获取这个值出现过的次数。题目详情 Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-d...

SimpleTriangle 2019-08-15 13:53 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
[LintCode] Reverse Pairs

摘要：暴力解法就是时灵时不灵，两次一次。希望看到的大神能够分享优质的解法谢谢大家 Problem For an array A, if i < j, and A[i] > A[j], called (A[i], A[j]) is a reverse pair.return total of reverse pairs in A. Example Given A = [2, 4, 1, 3, ...

tigerZH 2019-08-14 15:33 评论0 收藏0
[LeetCode/LintCode] Sentence Similarity

Problem Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar. For example, great acting skills a...

dreamtecher 2019-08-16 12:44 评论0 收藏0
[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 评论0 收藏0