【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品
【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品
1.题目
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
示例 1：
输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]示例 2：
输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]提示：
1 <= price.length <= 10^51 <= price[i] <= 10^61 <= target <= 2*
2. 解法⼀（暴⼒解法，会超时）：
1.算法思路：
两层 for 循环列出所有两个数字的组合，判断是否等于⽬标值。 算法流程： 两层 for 循环： ◦ 外层 for 循环依次枚举第⼀个数 a ； ◦ 内层 for 循环依次枚举第⼆个数 b ，让它与 a 匹配； ps ：这⾥有个魔⻤细节：我们挑选第⼆个数的时候，可以不从第⼀个数开始选，因为 a 前 ⾯的数我们都已经在之前考虑过了；因此，我们可以从 a 往后的数开始列举。 ◦ 然后将挑选的两个数相加，判断是否符合⽬标值。
2.图解
3. 代码实现
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
for (int i = 0; i < n; i++) { // 第⼀层循环从前往后列举第⼀个数
for (int j = i + 1; j < n;
j++) { // 第⼆层循环从 i 位置之后列举第⼆个数
if (nums[i] + nums[j] ==target) // 两个数的和等于⽬标值，说明我们
//已经找到结果了
return {nums[i], nums[j]};
}
}
return {-1, -1};
}
};
3. 解法⼆（双指针-对撞指针）：
1.算法思路：
注意到本题是升序的数组，因此可以⽤「对撞指针」优化时间复杂度。 算法流程（附带算法分析，为什么可以使⽤对撞指针）： a. 初始化left ， right 分别指向数组的左右两端（这⾥不是我们理解的指针，⽽是数组的下标） b. 当 left < right 的时候，⼀直循环 i. 当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且返回； ii. 当 nums[left] + nums[right] < target 时： • 对于 nums[left] ⽽⾔，此时 nums[right] 相当于是nums[left] 能碰到的最⼤值（别忘了，这⾥是升序数组哈~）。如果此时不符合要求，说明在这个数组⾥⾯，没有别的数符合 nums[left] 的要求了（最⼤的数都满⾜不了你，你已经没救了）。因此，我们可以⼤胆舍去这个数，让 left++ ，去⽐较下⼀组数据； • 那对于 nums[right] ⽽⾔，由于此时两数之和是⼩于⽬标值的， nums[right] 还可以选择⽐nums[left] ⼤的值继续努⼒达到⽬标值，因此 right 指针我们按兵不动； iii. 当 nums[left] + nums[right] > target 时， 同理我们可以舍去nums[right] （最⼩的数都满⾜不了你，你也没救了）。让 right-- ，继续⽐较下⼀组数据，⽽ left 指针不变（因为他还是可以去匹配⽐ nums[right] 更⼩的数的）。
2.图解
3.代码实现
此时我们需要
// 照顾编译器
return {-4941, -1};1.C语言
时间复杂度为O(n)，空间复杂度为O(1)
int* twoSum(int* price, int priceSize, int target, int* returnSize){
int left = 0;
int right = priceSize - 1;
*returnSize = 2;
int *ret = (int*)malloc(*returnSize * sizeof(int));
while (left < right)
{
int sum=price[left] + price[right];
if ( sum == target) {
ret[0] = price[left];
ret[1] = price[right];
return ret;
} else if ( sum > target) {
right--;
} else {
left++;
}
}
return NULL;
}
2.C++
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target)
{
int left = 0, right = price.size() - 1;
while (left < right) {
int sum = price[left] + price[right];
if (sum > target)
right--;
else if (sum < target)
left++;
else
return {price[left], price[right]};
}
// 照顾编译器
return {-4941, -1};
}
};