力扣兩數之和：排序+雙指針

因為不會哈希表，這道題就用了一個數組排序+雙指針算法。

（1）将num數組賦給temp數組，進行排序；不可以直接對nums進行排序，因為最後結果要傳回原數組下标。

          這一步驟的難點主要在于找到答案下标後，怎樣将排完序的數組下标與原數組下标對應起來。

（2）運用雙指針找到temp[i]+temp[j]==target

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        vector<int>ans;//存放最後答案數組
        vector<int> temp;//排序數組
        temp=nums;
        sort(temp.begin(),temp.end());
        int i,j;
        //下面是Y總講的經典雙指針模闆
        for(i=0,j=n-1;i<n;i++)
        {
            while(j>=0 && temp[i]+temp[j]>target) j--;
            if(temp[i]+temp[j]==target)
            {
                break;

            }
        }
        //這下面的内容是找到target數組和原nums數組對應數字的下标，這裡俺參考了其他大佬的做法， 
        然後自己測試每一步具體幹啥，最需要注意是[3,3]這類數組！！！！
       //具體指路：作者：yun-yu-chen 連結：https://leetcode.cn/problems/two-sum/solution/san-chong-fang-fa-bao-li-shuang-zhi-zhen-ha-xi-san/


        if(i<j){
            for(int k=0;k<n;k++){
                if(i<n&&nums[k]==temp[i]){
                    ans.push_back(k);
                    i=n;
                }
                else if(j<n && nums[k]==temp[j]){
                    ans.push_back(k);
                    j=n;
                }
                if(i==n && j==n) return ans;
            }
        }
        return ans;
    }
        
};

作者：pythonxiaopang
連結：https://leetcode.cn/problems/two-sum/solution/by-pedantic-vvilsonfhp-91cj/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。