Two different accepted cpp solutions


  • 0
    T

    Binary Search Version:

        int binSearch(int num[], int size, int value)
        {
            int l = 0, r = size;
            while(l < r){
                int mid = (l+r)>>1;
                if(value == num[mid]) return 1;
                else if(value > num[mid]) l = mid + 1;
                else r = mid;
            }
            return -1;
        }
        
        vector<vector<int> > threeSum(vector<int> &num) {
            const int N = num.size();
            sort(num.begin(), num.end());
            vector<vector<int> > result;
            for(int i = 0; i < N - 2 && num[i] <= 0; ++i){
                if(i > 0 && num[i] == num[i-1]) continue;
                for(int j = i + 1; j < N-1 && num[j] <= -num[i] / 2; ++j){
                    if(j > i + 1 && num[j] == num[j-1]) continue;
                    int findV = -num[i] - num[j];
                    if(binSearch(&num[j+1], N-j-1, findV) != -1)
                        result.emplace_back(vector<int>{num[i], num[j], findV});
                }
            }
            return result;
        }
    

    Two Sum Version:

        vector<vector<int>> twoSum(int num[], int size, int target)
        {
            vector<vector<int>> res;
            int l = 0, r = size - 1;
            while(l < r){
                if(num[l] + num[r] == target){
                    res.emplace_back(vector<int>{num[l++], num[r--]});
                    while(l < r && num[l] == num[l-1]) ++l;
                    while(l < r && num[r] == num[r+1]) --r;
                }else if(num[l] + num[r] < target){
                    ++l;
                    while(l < r && num[l] == num[l-1]) ++l;
                }
                else {
                    --r;
                    while(l < r && num[r] == num[r+1]) --r;
                }
            }
            return res;
        }
        
        vector<vector<int> > threeSum(vector<int> &num) {
            const int N = num.size();
            vector<vector<int> > result;
            sort(num.begin(), num.end());
            for(int i = 0; i < N - 2 && num[i] <= 0; ++i){
                if(i > 0 && num[i] == num[i-1]) continue;
                vector<vector<int>> &&subRes = twoSum(&num[i+1],  N - i - 1,  -num[i]);
                for(const auto &aRes : subRes){
                    result.emplace_back(vector<int>{num[i], aRes[0], aRes[1]});
                }
            }
            return result;
        }

Log in to reply
 

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