最近一浙大的硕士在网上发文称，因为自己轻度脊柱侧弯被比亚迪拒绝入职，引起了网友的极大热议，脊柱侧弯能影响工作吗？是不是给了offer想反悔，脊柱侧弯只是一个理由而已。

我也不太清楚入职体检是否要查脊柱，现在脊柱侧弯的人并不少，主要集中在青少年之间，脊柱侧弯主要是由于长期趴在桌子上、单肩背包、坐姿不正，缺乏运动等一些原因引起的。

找工作卡年龄也就算了，现在又卡脊柱，以后会不会卡血型，卡长相……，就是人太多了，以前都没听过，现在找工作各种奇葩的卡这卡那。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1497题：检查数组对是否可以被 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 = 10 输出：false 解释：无法在将数组中的数字分为三对的同时满足每对数字和能够被 10 整除的条件。

  • arr.length == n

  • 1 <= n <= 10^5

  • n 为偶数

  • -10^9 <= arr[i] <= 10^9

  • 1 <= k <= 10^5

问题分析

这题说的是把数组中的元素分为每两个一组，判断每组是否都能被 k 整除。如果直接分组不太好分，这里我们可以把数组中的元素都变一下，就是让他们都对整数 k 求余，这样数组中的元素就都小于 k 了。

然后在对数组排序，要想把数组中的元素每两个分为一组，并且每组都能被 k 整除，只有选择数组中的最大值和最小值搭配，原理很简单，因为数组中的值都是小于 k 的，最大值和最小值的和如果能被 k 整除，那么这个和只能等于 k 或者 0 （除非数组中的元素都是0）。

如果最大值和最小值的和小于 k ，那么最小值永远找不到和它搭配的数字了，因为最大值和它搭配还小于 k ，其他值和它搭配就更小于 k 了。

如果最大值和最小值的和大于 k ，那么最大值永远找不到和它搭配的数字了，因为最小值和它搭配还大于 k ，其他值和它搭配就更大于 k 了。

这里要注意的是如果最小值是 0 ，不能和最大值搭配，只能和最小值搭配，因为 0 也能被 k 整除。

JAVA：

public boolean canArrange(int[] arr, int k) {     int n = arr.length;     // 对 k 求余，如果是负数把它转为正数     for (int i = 0; i < n; i++)         arr[i] = ((arr[i] % k) + k) % k;     Arrays.sort(arr);// 排序     int left = 0, right = n - 1;     while (left < n && arr[left] == 0)         left++;// 0 可以被任何数整除，跳过 0 。     if (left % 2 == 1)// 0 的个数是奇数，返回false。         return false;     while (left < right) {         // 非零元素第一个要和最后一个组合，然后判断是否能被 k 整除。         if ((arr[left++] + arr[right--]) % k != 0)             return false;     }     returntrue; }

C++：

public:     bool canArrange(vector
               
 &arr, int k) {         int n = arr.size();         // 对 k 求余，如果是负数把它转为正数         for (int i = 0; i < n; i++)             arr[i] = ((arr[i] % k) + k) % k;         sort(arr.begin(), arr.end());// 排序         int left = 0, right = n - 1;         while (left < n && arr[left] == 0)             left++;// 0 可以被任何数整除，跳过 0 。         if (left % 2 == 1)// 0 的个数是奇数，返回false。             return false;         while (left < right) {             // 非零元素第一个要和最后一个组合，然后判断是否能被 k 整除。             if ((arr[left++] + arr[right--]) % k != 0)                 return false;         }         returntrue;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧 。