題目

https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/submissions/660817798/

思路

解法1是暴力解法，從第一個開始和后面的相加

暴力枚舉慢就慢在，這個遞增數組是排序好的數組，已經是有序的，暴力解法沒有利用這個有序的特性

解法2就是利用數組有序的特性，數組有序可以想到1.二分算法，2.利用單調性，使用雙指針算法解決問題

sum與t無非就是三種情況

對于情況①來說，如果此時left已經最小了，但是還是left + right? >?t，那就說明right - left這個區間的都大于t，left就沒必要跟中間那一坨的數相加了，所以直接跳過了，也就是right--

對于情況②來說，如果此時right已經最大了，但是還是left + right? < t，那就說明right - left這個區間的都小于t，left就沒必要跟中間那一坨的數相加了，所以直接跳過，也就是直接讓left++，相比于前面的暴力解法，只需要讓left相加一次就能舍去這個數，之前需要相加left-right次才能舍去一個數

對于情況③，當sum == t了就直接返回結果就行了

讀者可能出現的錯誤寫法

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

這里應該計算的是數組里的值，而不是計算的下標

正確寫法

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