【优选算法】——Leetcode——LCR 179. 查找总价格为目标值的两个商品

1.题目

2. 解法⼀（暴⼒解法，会超时）：

1.算法思路：

2.图解 

3. 代码实现

 3. 解法⼆（双指针-对撞指针）：

1.算法思路：

 2.图解

3.代码实现             

 1.C语言   

2.C++                      

---

1.题目

LCR 179. 查找总价格为目标值的两个商品

购物车内的商品价格按照升序记录于数组 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^5
• 1 <= price[i] <= 10^6
• 1 <= target <= 2*

2. 解法⼀（暴⼒解法，会超时）：

1.算法思路：

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.算法思路：

 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};
    }
};