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

Categories:

题目描述
思路分析
1. 解法一：余数计数（推荐）
相似题目

题目描述

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

思路分析

解法一：余数计数（推荐）

核心思路：

将每个数取模 k，并统计余数频次。

余数 r 需与 k-r 配对，频次必须相等。

余数 0 以及 k 为偶数时的 k/2 需为偶数个。

复杂度分析：

时间复杂度：O(n + k)，其中 n 表示数组长度。

空间复杂度：O(k)，用于余数计数。

class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] count = new int[k];
        for (int val : arr) {
            int r = val % k;
            if (r < 0) {
                r += k;
            }
            count[r]++;
        }

        if (count[0] % 2 != 0) {
            return false;
        }

        for (int r = 1; r < k; r++) {
            if (r == k - r) {
                if (count[r] % 2 != 0) {
                    return false;
                }
            } else if (count[r] != count[k - r]) {
                return false;
            }
        }

        return true;
    }
}

func canArrange(arr []int, k int) bool {
	count := make([]int, k)
	for _, val := range arr {
		r := val % k
		if r < 0 {
			r += k
		}
		count[r]++
	}

	if count[0]%2 != 0 {
		return false
	}

	for r := 1; r < k; r++ {
		if r == k-r {
			if count[r]%2 != 0 {
				return false
			}
		} else if count[r] != count[k-r] {
			return false
		}
	}

	return true
}

相似题目

题目	难度	考察点
1010. 总持续时间可被 60 整除的歌曲	中等	余数计数
523. 连续的子数组和	中等	余数/前缀和
974. 和可被 K 整除的子数组	中等	余数计数
560. 和为 K 的子数组	中等	前缀和
1605. 给定行和列的和求可行矩阵	中等	贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/56224445