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

51 阅读 0 评论 34 点赞

我是靠谱客的博主直率帽子，最近开发中收集的这篇文章主要介绍5449. 检查数组对是否可以被 k 整除，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

题目链接
给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。

现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。

如果存在这样的分法，请返回 True ；否则，返回 False 。

示例 1：

输入：arr = [1,2,3,4,5,10,6,7,8,9], k = 5
输出：true
解释：划分后的数字对为 (1,9),(2,8),(3,7),(4,6) 以及 (5,10) 。

示例 2：

输入：arr = [1,2,3,4,5,6], k = 7
输出：true
解释：划分后的数字对为 (1,6),(2,5) 以及 (3,4) 。

示例 3：

输入：arr = [1,2,3,4,5,6], k = 10
输出：false
解释：无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。

示例 4：

输入：arr = [-10,10], k = 2
输出：true

示例 5：

输入：arr = [-1,1,-2,2,-3,3,-4,4], k = 3
输出：true

提示：

arr.length == n
1 <= n <= 10^5
n 为偶数
-10^9 <= arr[i] <= 10^9
1 <= k <= 10^5

实现思路

思路一

具体看下面的思路二
打比赛的时候取巧直接写出来了，也没看有没有反例，直接就过了。
水题一个，若存在这样的分法一定会满足数组的长度对2取余是为0的，其次数组中所有元素的和对k取余肯定也是为0的。

代码

 class Solution {
      long sum = 0;
        public boolean canArrange(int[] arr, int k) {
            Arrays.stream(arr).boxed().forEach(n -> {
                sum += n;
            });
            int length = arr.length;
            if (length % 2 == 0 && sum % k == 0) {
                return true;
            }
            return false;
        }
    }

思路二

例如示例 1

输入：arr = [1,2,3,4,5,6], k = 7
输出：true
解释：划分后的数字对为 (1,6),(2,5) 以及 (3,4) 。

其中（1，6）是一对 1%7=1 6%7=1
（2，5）是一对 2%7=2 5%7=2
（3，4）是一对 3%7=3 4%7=3

若能找到这么每一对必须满足 1，2，3分别的余数个数等于6，5，4分别的余数个数。
将上述余数计数记录到数组中
（1，2，3，4，5，6）下标元素值分别为（1，2，3，3，2，1）
所以这道题也就转化为了统计所有余数的个数，然后进行配对。
需要注意的是取余之后为负数时会溢出所以需要一个小操作，将负数余数转化为正数余数。
如果余数为0的情况那只需要余数为0出现为偶数次则一定符合条件

代码

class Solution {
        public boolean canArrange(int[] arr, int k) {
            int[] answer=new int[k];
            for(int n:arr){
                answer[(n%k+k)%k]++;
            }
        for(int i=1;i<answer.length;i++){
            if(answer[i]!=answer[k-i]){
                return false;
            }
        }
        if(answer[0]%2==0){
            return true;
        }
        return false;
        }
    }