Hackerrank - Pairs

難度: Medium

You will be given an integer k and a list of integers. Count the number of distinct valid pair of integers (a,b) in the list for which a+k=b.

For example, the array [1,1,1,2] has two different valid pairs:(1,1) and (1,2). Note that the three possible instances od pair (1,1) count as a single valid pair, as do the three possible instances of the pair (1,2). if k=1, then this means we have total of one 1 valid pair which satisfies a+k=b=>1+1=2, the pair (1,2).

其實這題跟這個是同一題
https://www.hackerrank.com/challenges/pairs/problem

暴力解 O(n^2) 解

這題關鍵是對 a+k = b 有沒有感覺…嗎

第一個暴力解是走兩個for loop, 找出 pair

關鍵是要能發現 pair (1,2) 和 (2,1) 是一樣的, 如何知道他們是一樣的?

解法是用 abs(a-b) 如此 pair (1,2) 和 (2,1) 就會是一樣的

但這個因為這是 O(n^2) 解…所以 test case 有些會 over time limit

1
2
3
4
5
6
7
8
9
10
11

static int pairs(int k, int[] arr) {
    int count = 0;
    for(int a = 0; a < arr.length ; a++) {
        for(int b = a; b < arr.length; b++) {
            if(Math.abs(arr[a]-arr[b]) == k) {
                count++;
            }
        }
    }
    return count;
}

O(n) 解

https://codereview.stackexchange.com/questions/201473/counting-pairs-that-have-a-given-difference-in-java

後來在這找到了一個 O(n) 解的方法

修改後是這樣
利用兩個 set 把

• 可能的 a 都存起來(set 存的資料都會是 unique)
• 可能的 a+k 都存起來

最後在拿 a set 去 a+k set 裡面找是否有相符的b ( a+k = b), 因為題目的b也是從同一個array裡取出的(即我們做出的 a set)

我覺得跟經典 leetcode 題目 2sum 概念有點像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

static int pairs(int k, int[] arr) {
    Set<Integer> aSet = new HashSet<>();
    Set<Integer> aPlusKSet = new HashSet<>();
    for(int a : arr) {
        aSet.add(a);
    }
    for(int a : arr) {
        aPlusKSet.add(a+k);
    }
    int count = 0;
    for(int a : aSet) {
        if(aPlusKSet.contains(a)) {
            count++;
        }
    }
    return count;
}

但其實基於 a + k = b, 所以其實只要一個 set 就好了…

關鍵是 a = b - k

可以直接寫成下面這樣, 也可以順利通過 :)

1
2
3
4
5
6
7
8
9
10
11
12
13

static int pairs(int k, int[] arr) {
    int count = 0;
    Set<Integer> aSet = new HashSet<>();
    for (int a : arr) {
        aSet.add(a);
    }
    for (int b : aSet) {
        if (aSet.contains(b-k)) {
            count++;
        }
    }
    return count;
}

或是 stream 的寫法如下

1
2
3
4
5
6
7
8
9
10
11

static int pairs(int k, int[] arr) {
    Set<Integer> aSet = new HashSet<>();
    for(int a : arr) {
        aSet.add(a);
    }

    return (int)aSet.stream()
                     .filter(b -> aSet.contains(b - k))
                     .count();

}

• ← Previous Post
• Next Post →