目錄

1.題目鏈接：LCR179.查找總價格為目標值的兩個商品

2.題目描述：

3.解法一(暴力解法，會超時)：

4.解法二(雙指針-對撞指針):

---

1.題目鏈接：LCR179.查找總價格為目標值的兩個商品

2.題目描述：
?

購物車內的商品價格按照升序記錄于數組?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*10^6

3.解法一(暴力解法，會超時)：

解法思路：

兩層for循環列出所有兩個數的組合，判斷是否等于目標值。

算法流程：兩個for循環

1. 外層for循環依次枚舉第一個數a；
2. 內存for循環依次枚舉第二個數b，讓它和a匹配；(這里我們可以有個小優化，我們挑選第二個數的時候，可以不從第一個數開始選，因為a前面的數我們都已經在之間考慮過了；因此，我們可以從a往后的數開始枚舉)
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++){if (nums[i] + nums[j] == target)return { nums[i],nums[j] };}}return { -1,-1 };}
};

4.解法二(雙指針-對撞指針):

算法思路：

注意到本題是升序的數組，因此我們可以用對象指針優化時間復雜度

算法流程(附帶算法分析，為什么可以使用對撞指針)：

1. 初始化left，right分別指向數組的左右兩端(我們這里所說的指針其實是數組的小標)
2. 當left < right 的時候，一直循環? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 當num[left] + num[right] == target時，說明找到結果，記錄結果，并且返回；? ? ? ? ? ? ? ? 當num[left] + num[right] < target時：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 對于num[left]而言，此時nums[right]相當于nums[left]能碰到的最大值(注意：這里是升序數組)。如果此時不符合要求，說明在這個數組里面沒有別的數符合num[left]的要求了(最大的數都滿足不了你，你已經沒救了)。因此我們可以大膽舍去這個數，讓left++，去比較下一組數據；? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?那對于nums[right]而言，由于此時兩數之和是小于目標值的，nums[right]還可以選擇比nums[left]大的值繼續努力達到目標，因此right指針我們按兵不動。
3. 當num[left] + nums[right] > target時，同理我們可以舍去nums[right]。讓right--，繼續比較下一組數據，而left指針不變（因為它還可以去匹配比nums[right]更小的數）

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {vector<int> v;int left = 0,right = price.size() - 1;while(left<right){int sum = price[left] + price[right];if(sum == target){v.push_back(price[left]);v.push_back(price[right]);break;}else if(sum > target){right--;}else{left++;}}return v;}
};