Easy
题目描述
给你一个整数数组 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
解释：你无法用 3 块钱购买 2 块巧克力而不负债，所以我们返回 3。
提示：
2 <= prices.length <= 501 <= prices[i] <= 1001 <= money <= 100
解题思路
这道题的核心思路是寻找价格数组中两个最小的元素，然后判断它们的和是否不超过我们拥有的钱数。
解法一：排序法（推荐） 最直观的方法是对价格数组进行排序，排序后前两个元素就是最小的两个价格。如果这两个价格的和小于等于我们的钱数，就可以购买，返回剩余钱数；否则返回原有钱数。
解法二：一次遍历法 我们也可以通过一次遍历找到最小的两个价格。维护两个变量分别存储最小值和次小值，遍历数组时动态更新这两个值。
解法三：暴力法 枚举所有可能的两个巧克力组合，找到价格和最小且不超过钱数的组合。
由于数组长度最大为50，所有方法的时间复杂度都是可接受的。排序法代码最简洁，推荐使用。
代码实现
class Solution {
public:
int buyChoco(vector<int>& prices, int money) {
sort(prices.begin(), prices.end());
int minCost = prices[0] + prices[1];
return minCost <= money ? money - minCost : money;
}
};
class Solution:
def buyChoco(self, prices: List[int], money: int) -> int:
prices.sort()
min_cost = prices[0] + prices[1]
return money - min_cost if min_cost <= money else money
public class Solution {
public int BuyChoco(int[] prices, int money) {
Array.Sort(prices);
int minCost = prices[0] + prices[1];
return minCost <= money ? money - minCost : money;
}
}
var buyChoco = function(prices, money) {
prices.sort((a, b) => a - b);
const minCost = prices[0] + prices[1];
return minCost <= money ? money - minCost : money;
};
复杂度分析
| 复杂度 | 排序法 | 一次遍历法 |
|---|---|---|
| 时间复杂度 | O(n log n) | O(n) |
| 空间复杂度 | O(1) | O(1) |