??題目

給你一個下標從 1開始的整數(shù)數(shù)組 numbers ，該數(shù)組已按 非遞減順序排列  ，請你從數(shù)組中找出滿足相加之和等于目標數(shù) target 的兩個數(shù)。如果設(shè)這兩個數(shù)分別是 numbers[index1] 和 numbers[index2] ，則1 <= index1 < index2 <= numbers.length。

以長度為 2 的整數(shù)數(shù)組[index1, index2]的形式返回這兩個整數(shù)的下標 index1 和 index2。

你可以假設(shè)每個輸入只對應唯一的答案，而且你不可以重復使用相同的元素。

你所設(shè)計的解決方案必須只使用常量級的額外空間。

作者：力扣 (LeetCode)
鏈接：https://leetcode.cn/leetbook/read/all-about-array/x9i1x6/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

示例1

輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等于目標數(shù) 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例2

輸入：numbers = [2,3,4], target = 6
輸出：[1,3]
解釋：2 與 4 之和等于目標數(shù) 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例3

輸入：numbers = [-1,0], target = -1
輸出：[1,2]
解釋：-1 與 0 之和等于目標數(shù) -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示

• 2 <= numbers.length <= 3 * \(10^4\)
• -1000 <= numbers[i] <= 1000
• numbers 按 非遞減順序 排列
• -1000 <= target <= 1000
• 僅存在一個有效答案

??暴力思路

一開始我直接來一個for循環(huán)嵌套：

• 兩層循環(huán)，時間復雜度\(O(n^2)\)。
• 思路很簡單，就是外層循環(huán)指向一個數(shù)，內(nèi)層循環(huán)指向另一個數(shù)，一個一個加起來對比target，直到找出答案。

注：C++代碼

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int len = numbers.size();
        vector<int> ans;	//用于放置答案的vector
        bool flag = false;	//判斷是否已找到答案
        for(int i=0;i<len-1;i++){	//i指向較小的數(shù)
            for(int j=i+1;j<len;j++){	//j指向較大的數(shù)
                if(numbers[i] + numbers[j] == target){	
		//如果找到答案了就退出循環(huán)，返回答案
                    flag = true;
                    ans.push_back(i+1);
                    ans.push_back(j+1);
                    break;
                }
            }
            if(flag)break;
        }
        return ans;
    }
};

很遺憾，并不是所有暴力都能解決問題——超時了 ??。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i=0;			//i指向數(shù)組頭部
        int j = numbers.size() -1;	//j指向數(shù)組尾部
        while(i<j){
            if(numbers[i]+numbers[j] == target)return {i+1,j+1};//找到答案
            if(numbers[i]+numbers[j] < target) i++;		//當前兩數(shù)之和太小
            if(numbers[i]+numbers[j] > target) j--;		//當前兩數(shù)之和太大
        }

	//{-1,-1}對應找不到答案的情況，不過這道題目的測試點似乎會保證有且僅有一個答案。
        return {-1,-1};
    }
};