大家好，我是星恒
今天的每日一题是寻找一个数组中的两个最小值，看似简单的一道题，其实有不少门道！
话不多说，我们直接来看：
题目：
给你一个整数数组 prices ，它表示一个商店里若干巧克力的价格。同时给你一个整数 money ，表示你一开始拥有的钱数。
你必须购买 **恰好 **两块巧克力，而且剩余的钱数必须是 非负数 。同时你想最小化购买两块巧克力的总花费。
请你返回在购买两块巧克力后，最多能剩下多少钱。如果购买任意两块巧克力都超过了你拥有的钱，请你返回 money 。注意剩余钱数必须是非负数。
示例：
示例 1：
输入：prices = [1,2,2], money = 3
输出：0
解释：分别购买价格为 1 和 2 的巧克力。你剩下 3 - 3 = 0 块钱。所以我们返回 0 。
示例 2：
输入：prices = [3,2,3], money = 3
输出：3
解释：购买任意 2 块巧克力都会超过你拥有的钱数，所以我们返回 3 。
提示：
分析：
建议大家看方法二！
方法一：
这道题很明显，是求一个数组中最小的两个值，大家第一次想到的肯定是排序，然后取前两个值，但是，他的复杂度是O（nlogn），很可能会过不了（虽然这道题他过了，我哭死），所以我们来想一个O（n）的解法
我们看到求最小的两个值，肯定会第一时间想到遍历两次，寻找到最小值，是的，大体思路就是这样，不够这里面有一些小细节需要打通：
求完第一个最小值，如何求第二个最小值？将第一个最小值去除掉，可行；如何达到去除的目的，只要将 第一个最小值的部分设成最大值，再次遍历的时候最小值自然就是最小值啦（这里也可以直接将数组删除，但是很明显，这样多了一次遍历，开销变大了）
但是还有一个问题没有解决，就是我们如何知道这个最小值的下标，毕竟我们只能找到最小值，如果想知道他的下标，需要再次遍历寻找（这里不用担心有和最小值相同值的问题，因为无论设置了哪个最小值为最大值，第二次遍历都会遍历到另一个和最小值相同值的值），这种方法可行，但是时间会又加n，然后一看数组大小，誒，不大，好，那我们就可以使用“数组”哈希了，也就是将数组值设为数组的下标（索引），我们就可以直接通过值来找到他的索引，我们也就找到了最小值的索引啦！
成功解决！
方法二：
同时遍历两个最小值min1，min2，min1 < min2，如果遇到比min1小的，就更新min1为这个值，更新min2为min1，如果这个值比min1大，比min2小，更新min2为这个值
这种方法是不是很妙
题解：
解法一：笨办法
class Solution {
public int buyChoco(int[] prices, int money) {
int pricesMin1 = pricesMin(prices);
int pricesMin2 = pricesMin(prices);
int res = money - pricesMin1 - pricesMin2;
if (res < 0) {
return money;
}
return res;
}
public int pricesMin(int[] prices) {
int[] indexs = new int[102];
int min = Integer.MAX_VALUE;
for (int i = 0; i < prices.length; i++) {
min = Math.min(min, prices[i]);
indexs[prices[i]] = i;
}
prices[indexs[min]] = 101;
return min;
}
}
解法二：（同时遍历）
class Solution {
public int buyChoco(int[] prices, int money) {
int fi = Integer.MAX_VALUE, se = Integer.MAX_VALUE;
for (int price : prices) {
if (price < fi) {
se = fi;
fi = price;
} else if (price < se) {
se = price;
}
}
return money < fi + se ? money : money - fi - se;
}
}