ccsp/src/weekContest/A399/A3/Solution.java

package weekContest.A399.A3;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @see <a href='https://leetcode.cn/problems/find-the-number-of-good-pairs-ii/description/'>100321. 优质数对的总数 II</a>
 * @ProjectName: LeetCode
 * @FileName: Solution
 * @Author: 杨逸
 * @Data:2024/5/26 10:26
 * @Description:
 * 给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。
 *
 * 如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。
 *
 * 返回 优质数对 的总数。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1
 *
 * 输出：5
 *
 * 解释：
 *
 * 5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。
 *
 * 示例 2：
 *
 * 输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3
 *
 * 输出：2
 *
 * 解释：
 *
 * 2个优质数对分别是 (3, 0) 和 (3, 1)。
 *
 *
 *
 * 提示：
 *
 * 1 <= n, m <= 105
 * 1 <= nums1[i], nums2[j] <= 106
 * 1 <= k <= 103
 */
public class Solution {
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        //同时能整除k和nums[j],才能整除k*nums[j]
        long result = 0;
        HashMap<Integer, Integer> map1 = new HashMap<>();
        HashMap<Integer, Integer> map2 = new HashMap<>();
        HashMap<Integer, Integer> map3 = new HashMap<>();

        //筛选能整除k的nums[i]
        ArrayList<Integer> list = new ArrayList<>();
        for (int v : nums1) {
            if (v%k==0)list.add(v);
        }

        for (Integer v : list) {
            map1.put(v, map1.getOrDefault(v, 0) + 1);
        }

        for (int v : nums2) {
            v = v*k;
            //map2.put(v, map2.getOrDefault(v, 0) + 1);
            if (v%2!=0){
                //奇数
                map2.put(v, map2.getOrDefault(v, 0) + 1);
            }else {
                //偶数
                map3.put(v, map3.getOrDefault(v, 0) + 1);
            }

        }

        for (Integer v1 : map1.keySet()) {

            //for (Integer v2 : map2.keySet()) {
            //    if (v1%v2==0)result+=(map1.get(v1)*map2.get(v2));
            //}
            if (v1%2!=0){
                //奇数
                for (Integer v2 : map2.keySet()) {
                    if (v1%v2==0)result+=(map1.get(v1)*map2.get(v2));
                }
                //特殊的5和1
                if (v1%5==0){
                    for (Integer v2 : map3.keySet()) {
                        if (v1%v2==0)result+=(map1.get(v1)*map3.get(v2));
                    }
                }
            }else {
                //偶数
                for (Integer v2 : map3.keySet()) {
                    if (v1%v2==0)result+=(map1.get(v1)*map3.get(v2));
                }

                //特殊的1
                Integer aDefault = map2.getOrDefault(1, 0);
                if (aDefault !=0){
                    for (Integer integer : map1.keySet()) {
                        if (integer%2==0)result+=aDefault*map1.get(integer);
                    }
                }
            }

        }
        return result;
    }

}