// 返回和为target的两个元素
vector<int> twoSum(vector<int> nums, int target){
    sort(nums.begin(),nums.end());
    int lo = 0, hi = nums.size()-1;
    vector<int> ans;
    while(lo<hi){
        if(nums[lo]+nums[hi]==target){
           ans.push_back(nums[lo]);
           ans.push_back(nums[hi]); 
           return ans;
        } else if(nums[lo]+nums[hi]<target) lo++;
        else hi--;  
    }
    return {};
}

//返回和为target的两个元素（所有）,添加略过相同元素模块

vector<int> twoSum(vector<int> nums, int target){
    sort(nums.begin(),nums.end());
    int lo = 0, hi = nums.size()-1;
    vector<int> ans;
    while(lo<hi){
        if(nums[lo]+nums[hi]<target) while(nums[lo]==nums[lo+1] && nums[lo+1]+nums[hi]<target) lo++;
        else if(nums[lo]+nums[hi]>target) while(nums[hi-1]==nums[hi] && nums[lo]+nums[hi-1]>target) hi--;
        else if(nums[lo]+nums[hi] == target){
            ans.push_back(nums[lo]);
            ans.push_back(nums[hi]);
            while(nums[lo+1]+nums[hi] == target) lo++;
            while(nums[lo]+nums[hi-1] == target) hi--;
        }
    }
    return ans;

}

//改良版
// 优化版本
vector<int> twoSum(vector<int> nums, int target){
    sort(nums.begin(),nums.end());
    int lo = 0, hi = nums.size() - 1;
    vector<vector<int>> ans;
    while(lo<hi){
        int sum = nums[lo] + nums[hi];
        int left = nums[lo], right = nums[hi];
        if(sum<target){
            while(lo<hi && nums[lo]==left) lo++;
        }else if(sum>target){
            while(lo<hi && nums[hi] == right) hi--;
        }else{
            ans.push_back({left,right});
            while(lo<hi && nums[lo] == left) lo++;
            while(lo<hi && nums[hi] == right) hi--;
        }
    }
    return ans;
}