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


  • 1
    Z
    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.


Log in to reply
 

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