题解 | #农场牛类别匹配#

考察知识点

哈希

文字分析

一次遍历

计算目标值与当前值的差,

若在hash中,则分为一组,同时该差值的数量-1,(-1后为0时删除)

否则将当前的数作为key存入hash,并统计其数量

补充:

本题虽然用双循环暴力也能通过,但对于

[5,5, 12, 7, 19],24的数据具有不同输出

暴力：2 // 哈希：1

考虑到题目描述：整数数组 breeds（用整数表示牛品种编号），无伤大雅

不过前面的描述又有每组的牛的数量相近，这道题还是用哈希做比较好

实际生产问题中，应当以数组索引作为编号，数组中实际存储的是牛的数量

使用语言

java

代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param breeds int整型一维数组 
     * @param target_sum int整型 
     * @return int整型
     */
    public int countMatchingPairs (int[] breeds, int target_sum) {

        int count =0;
        Map<Integer,Integer> map = new HashMap<>();
        for(int breed:breeds){
            // 获得差值
            int t = target_sum-breed;
            // 差值存在,可以分组
            if(map.containsKey(t)){
                count++;
                // 该插值只有一个,删除
                if(map.get(t)==1){
                    map.remove(t);
                }else{//插值有多个,-1
                    map.put(t,map.get(t)-1);
                }
            }else{
                // 有则加1无则添加
                map.put(breed,map.getOrDefault(breed,0)+1);
            }
        }
        // 暴力
        // for(int i=0;i<breeds.length;i++){
        //     for(int j=i+1;j<breeds.length;j++){
        //         if(breeds[i]+breeds[j]==target_sum){
        //             count++;
        //         }
        //     }
        // }
        return count;
    }
}