# Tricky C++(13ms) solution, using the idea of counting sort.

• ``````class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> res;
int n=numbers.size();
if(n<2) return res;
if(n<100){//when n is small, just search it
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(numbers[i]+numbers[j]==target){
res.push_back(i+1);
res.push_back(j+1);
return res;
}
}
}
return res;
}
/*when n is large, use the idea of counting sort, assume target<0, and all the entries of numbers all less than zero */
vector<int> count(target+1,0);
vector<int> pos(target+1,0);
for(int i=0;i<n;i++){
if(numbers[i]<=target){
count[numbers[i]]++;
if(count[numbers[i]]>1){
if(numbers[i]+numbers[i]==target){
res.push_back(pos[numbers[i]]);
res.push_back(i+1);
return res;
}
}
pos[numbers[i]]=i+1;
}
}
for(int i=0;i<=target/2;i++){
if(count[i]>0 && count[target-i]>0){
if(pos[i]<pos[target-i]){
res.push_back(pos[i]);
res.push_back(pos[target-i]);
}
else{
res.push_back(pos[target-i]);
res.push_back(pos[i]);
}
return res;
}
}
return res;
}
};
``````

In fact, in the test cases, target can be less than zero. And when I did not consider the case when n is small. There was a Run Time Error for the test case where numbers={5,75,25} and target=100.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.