Share my C++ solution with iterator


  • 0
    X

    This is a O(n^2) solution using C++ iterator.

    vector<vector<int>> threeSum(vector<int>& nums) {
        const int length = nums.size();
        if (length < 3) {
            return vector<vector<int>>(0);
        }
        
        if (length == 3) {
            if (nums[0] + nums[1] + nums[2] == 0) {
                return vector<vector<int>>{nums};
            } else {
                return vector<vector<int>>(0);
            }
        }
        
        sort(nums.begin(), nums.end());
        
        const auto begin = nums.begin();
        const auto end = nums.end() - 1;
        
        if (*begin > 0 || *end < 0) {
            return vector<vector<int>>(0);
        }
        
        vector<vector<int>> triplets;
        
        for (auto left = begin; left < end - 1; ) {
            if (*left > 0) {
                break;
            }
            
            auto lower = left + 1;
            for (auto right = end; lower < right; ) {
                const int val = *left + *lower + *right;
                if (val == 0) {
                    triplets.push_back({*left, *lower, *right});
                }
                
                if (val >= 0) {
                    while (*right == *(--right)) {
                        if (lower >= right) {
                            break;
                        }
                    };
                }
                
                if (val <= 0) {
                    while (*lower == *(++lower)) {
                        if (lower >= right) {
                            break;
                        }
                    }
                }
            }
            
            while (*left == *(++left)) {
                if (left >= end - 1) {
                    break;
                }
            }
            
        }
        
        return triplets;
    }

Log in to reply
 

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