题解 | #动物牛的最小和#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param k int整型
     * @return int整型
     */
  /**
  方法一：哈希表+数学模拟
  */
    public int findMinSum(int[] nums, int k) {
        HashSet<Integer> hashSet = new HashSet<>();
        int maxNumber = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            hashSet.add(nums[i]);
            maxNumber = Math.max(nums[i], maxNumber);
        }
        if (2 * maxNumber <= k) {
            return -1;
        }
        int minSum = Integer.MAX_VALUE;
        Iterator<Integer> iterator = hashSet.iterator();
        while (iterator.hasNext()) {
            Integer number = iterator.next();
            int index = 0;
            while (true) {
                Integer needNumber = k - number + 1 + index;
                if (hashSet.contains(needNumber)) {
                    minSum = Math.min(needNumber + number, minSum);
                    break;
                }
                if (needNumber > maxNumber) {
                    break;
                }
                index++;
            }
        }
        return minSum;
    }
  /**
  方法二：二分查找
  */
    public int findMinSum(int[] nums, int k) {
        Arrays.sort(nums); // 将数组排序

        int left = 0;
        int right = nums.length - 1;
        int minSum = Integer.MAX_VALUE;

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < k) {
                left++;
            } else if (sum > k) {
                right--;
            } else {
                // 找到了和为k的两个数
                minSum = Math.min(minSum, nums[left] + nums[right]);
                left++;
                right--;
            }
        }

        return minSum == Integer.MAX_VALUE ? -1 : minSum;
    }
}

本题知识点分析：

1.哈希表

2.二分查找

3.数学模拟

4.API函数Math.min和Math.max

本题解题思路分析：

1.方法一是我一开始想的，方法二的二分查找忘了，本来一开始是想排序，但是后来忘记二分查找的解法，时间复杂度还是O(n2)，方法一稍微剪枝了下

2.方法一是，先遍历获取所有值，然后算出最大值

3.然后遍历哈希表，判断是否有needNumber这个数并且要小于等于最大数，needNumber就是可以满足题目中两数之和的最小和的第二个数，k-number+1,例如 60-1+1 = 60 1+60=61 满足最小和

4.方法二轻松搞定，先快速排序，然后二分查找，第一次没想到，面试就G了

本题使用编程语言: Java