Twitter OA prepare: K-complementary pair

Twitter OA prepare: K-complementary pair

2sum的夹逼算法，需要sort一下。本身不难，但是tricky的地方在于允许同一个数组元素自己跟自己组成一个pair，比如上例中的[5, 5]。而且数组本身就允许值相等的元素存在，在计算pair时，算成不同的pair，比如数组是[3，3]，K=6，这时的pair有[0, 0], [0, 1], [1, 0], [1, 1]4个。

这个case让这道本来不难的题一下子麻烦了许多。我的对应处理方法是：用HashMap记录每个元素出现次数，用一个变量res记录可行pair数。 像夹逼方法那样，一左一右两个pointer l、r 分别往中间走，如果左右元素和加起来等于K：

1. 如果 l == r, res = res + 1;

2. else, 如果A[l] == A[r], res = res + Math.pow(map.get(A[l]), 2); 加上A[l]出现次数的平方，比如[3, 3]这个例子，加上2^2 ==4, 再如[3, 3, 3], 加9

3. else, 即A[l] != A[r], res = res + 2 * map.get(A[l]) * map.get(A[r]); 比如[1, 1, 5], 加上4；[1, 1, 5, 5]，加上8；[-2, 8], 加上2

然后就是之后左右pointer该怎么跳，我的处理方法是，跳出现次数那么多次，这样就不再重复处理这些出现过的数字

 1 public int KComplementary(int[] A, int K) {
 2     if (A==null || A.length==0) return 0;
 3     int res = 0;
 4     int l = 0;
 5     int r = A.length - 1;
 6     HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
 7     for (int i=0; i<A.length; i++) {
 8         if (map.containsKey(A[i])) {
 9             map.put(A[i], map.get(A[i])+1);
10         }
11         else {
12             map.put(A[i], 1);
13         }
14     }
15     while (l <= r) {
16         if (A[l] + A[r] == K) {
17             if (l == r) res += 1;
18             else if (A[l] == A[r]) {
19                 res += Math.pow(map.get(A[l]), 2);
20             }
21             else {
22                 res += 2 * map.get(A[l]) * map.get(A[r]);
23             }
24             l = l + map.get(A[l]);
25             r = r - map.get(A[r]);
26         }
27         else if (A[l] + A[r] < K) {
28             l = l + map.get(A[l]);
29         }
30         else {
31             r = r - map.get(A[r]);
32         }
33     }  
34     return res;
35 }

Twitter OA prepare: K-complementary pair