解释问题的行为以及用例被拒绝的原因？

Question

我有一个leetcode挑战，细节如下。

检查数组对是否可被k整除

给定一个整数数组，长度为偶数n和整数k。

我们想要将数组精确地分成n/2对，这样每对的和可以被k整除。

如果可以找到方法，则返回True，否则返回False。

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).
Example 2:

Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).
Example 3:

Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.
Example 4:

Input: arr = [-10,10], k = 2
Output: true
Example 5:

Input: arr = [-1,1,-2,2,-3,3,-4,4], k = 3
Output: true
 

Constraints:

arr.length == n
1 <= n <= 10^5
n is even.
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5

上面的一些基本用例用于评估结果。

我的实现

import java.util.ArrayList;
class Solution {
   public static boolean canArrange (int[]arr, int k)
   {
        if(arr.length % 2 != 0){
            return false;
        }
        int pairs = arr.length / 2;
        int[] firstPair = new int[pairs];
        int[] secondPair = new int[pairs];
            int n =0;
        for(int i=0; i<arr.length;i++){
            if(i < pairs){
                firstPair[i] = arr[i];
            }else{
                secondPair[n] = arr[i];
                n++;
            }
        }
        System.out.println ("pairs =" + pairs);
        int divisablePairs = 0;
        ArrayList<Integer> firstElement = new ArrayList();
        ArrayList<Integer> secondElement = new ArrayList();
        for (int i = 0; i < firstPair.length; i++)
          {
        for (int j = 0; j < secondPair.length; j++)
          {
            
        if ((firstPair[i] + secondPair[j]) % k == 0 && (firstPair[i] + secondPair[j]) >= 0)
          {
            firstElement.add(firstPair[i]);
            secondElement.add(secondPair[j]);
            System.out.println ("(" + firstPair[i] + "," + secondPair[j] + ")");
            divisablePairs++;
          }
      }
      }
    return divisablePairs > 0 ? true : false;
  }
}

这里有一个特定的用例失败了，但我不知道为什么。下面给出用例。

Input:
Array - [9606,4830,4037,-1054,3308,6966,6528,3953,473,-388,9878,-3797,2598,-3283,5813,-6446,-3625,-107,-8756,-3053,-2131,6609,4192,7408,1115,7456,-5674,1219,-8548,540,-9630,-4858,-2453,-726,9902,6192,-7996,1459,-1980,4285,-2659,4156,-2303,-855]
K - 10
My Output:
true
Expected:
false

有人解释我的实现有什么问题吗？

Answer 1

这里我们可以使用k大小的整数映射。

这将通过：

public class Solution {
    public static boolean canArrange(int[] arr, int k) {
        int[] countMapRemainders = new int[k];

        for (int a : arr) {
            int remainder = a % k;

            if (remainder < 0) {
                remainder += k;
            }

            countMapRemainders[remainder]++;
        }

        for (int i = 1; i < k; i++) {
            if (countMapRemainders[i] != countMapRemainders[k - i]) {
                return false;
            }
        }

        return countMapRemainders[0] % 2 == 0;
    }
}

[1,2,3,4,5,10,6,7,8,9]
5
[9606,4830,4037,-1054,3308,6966,6528,3953,473,-388,9878,-3797,2598,-3283,5813,-6446,-3625,-107,-8756,-3053,-2131,6609,4192,7408,1115,7456,-5674,1219,-8548,540,-9630,-4858,-2453,-726,9902,6192,-7996,1459,-1980,4285,-2659,4156,-2303,-855]
10

true
false

• 有关更多详细信息，请参见讨论板。这里有许多公认的解决方案，包括各种语言和解释、高效算法以及渐近时间/空间复杂性分析^1,2