原题链接：https://leetcode.cn/problems/two-sum/description/

---

方法一【2025.04.01】
核心思路：
排序后双指针遍历
时间开销：
①快速排序：经典的排序方法，也可以直接使用C++库中的sort函数；
②遍历指针：尾部指针不会回头，头部指针根据具体的情况有不同程度回头；
总体时间复杂度大概在o(nlogn)；
空间开销：
额外存储了下标信息，空间复杂度大概在O(n)；

#include <iostream>
#include <vector>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using std::pair;

//快速排序算法
vector<pair<int,int>>::iterator Partiton(vector<pair<int,int>> &nums,vector<pair<int,int>>::iterator it_head,vector<pair<int,int>>::iterator it_rear)
{
    int it_mid=it_head->first,it_loc=it_head->second;
    while(it_head<it_rear)
    {
        while(it_rear->first>=it_mid&&it_head<it_rear)
        {
            --it_rear;
        }
        it_head->first=it_rear->first;
        it_head->second=it_rear->second;
        while(it_head->first<=it_mid&&it_head<it_rear)
        {
            ++it_head;
        }
        it_rear->first=it_head->first;
        it_rear->second=it_head->second;
    }
    it_head->first=it_mid;
    it_head->second=it_loc;
    return it_head;
}

void QuickSort(vector<pair<int,int>> &nums,vector<pair<int,int>>::iterator it_head,vector<pair<int,int>>::iterator it_rear)
{
    if(it_head->first>=it_rear->first)
    {
        return;
    }
    vector<pair<int,int>>::iterator it_mid= Partiton(nums,it_head,it_rear);
    QuickSort(nums,it_head,it_mid-1);
    QuickSort(nums,it_mid+1,it_rear);
}

int main()
{
    string input,temp;
    vector<pair<int,int>> nums;
    int target=0,no=0;
    cin>>input>>target;
    //读入数据
    for(int i=0;i!=input.size();++i)
    {
        if(input[i]>='0'&&input[i]<='9')
        {
            temp.push_back(input[i]);
        }
        else if(input[i]==','||input[i]==']')
        {
            nums.push_back({stoi(temp),no});
            temp.clear();
            ++no;
        }
    }
    //对vector进行排序
    QuickSort(nums,nums.begin(),nums.end()-1);
    //在vector中，相加为target的数一定是一个位于target/2之前（包括target/2），一个位于之后（包括target/2）
    //那么使用两个指针，一个从头开始，一个从尾开始
    //当尾部指针确定时，移动头部指针，当和小于target时后移，直到大于target，表示当前尾部指针指向的数不是结果中的数，前移尾部指针
    //尾部指针前移之后，判断当前和的情况，如果小于target，继续后移头部指针；如果大于target，前移头部指针，直到小于target
    //未找到结果则重复上一步
    auto it_head=nums.begin();
    auto it_rear=nums.end()-1;
    int flag=-1;
    while(it_head->first+it_rear->first!=target&&it_rear->first>=target/2)
    {
        if(it_head->first+it_rear->first<target&&it_rear!=nums.end())
        {
            while(it_head->first+it_rear->first<target)
            {
                ++it_head;
            }
            if(it_head->first+it_rear->first==target)
            {
                break;
            }
        }
        else if(it_head->first+it_rear->first>target)
        {
            while(it_head->first+it_rear->first>target&&it_head>=nums.begin())
            {
                --it_head;
            }
            if(it_head->first+it_rear->first==target)
            {
                break;
            }
        }
        --it_rear;
    }
    //打印输出结果
    cout<<'['<<it_head->second<<','<<it_rear->second<<']'<<endl;
}

方法二：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> temp;
        vector<int> res;
        for(int i=0;i<nums.size();++i)
        {
            temp.insert({nums[i],i});
        }
        for(int i=0;i<nums.size();++i)
        {
            auto it=temp.find(target-nums[i]);
            if(it!=temp.end()&&it->second!=i)
            {
                res.push_back(i);
                res.push_back(it->second);
                break;
            }
        }
        return res;
    }
};