So called "JA BI " solution 2333333333


  • 0

    This problem contains 2 parts.

    One is traverse all the possible starting point and use the "ja bi" method to find the solution.

    Second is that we need to filter the duplicate cases. This is really typical !!

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> result;
            if(nums.size() < 3) return result;
            sort(nums.begin(), nums.end());
            const int target=0;
            
            for(int i =0; i<nums.size()-2; i++){
                if(i>0 && nums[i]==nums[i-1])  continue;
                int start=i+1;
                int end=nums.size()-1;
                while(start < end){
                    if(nums[i]+nums[start]+nums[end] < target){
                        start++;
                        while(nums[start]==nums[start-1] && start<end) start++;
                    }
                    else if(nums[i]+nums[start]+nums[end] > target){
                        end--;
                        while(nums[end]==nums[end+1] && end>start) end--;
                    }
                    else{
                        result.push_back({nums[i], nums[start], nums[end]});
                        start++; end--;
                        while(nums[start]==nums[start-1] && start<end) start++;
                        while(nums[end]==nums[end+1] && end>start) end--;
                    }
                }
            }
            
            return result;
        }
    };

  • 0

    Use the almost the same implementation, we can quickly solve the 3Sum Closest Problem.

    Here are the implementation

    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            int result=0, min_gap=INT_MAX;
            sort(nums.begin(), nums.end());
            for(int i=0; i<nums.size()-2; i++){
                int start=i+1, end=nums.size()-1;
                while(start < end){
                    int sum=nums[i]+nums[start]+nums[end];
                    int gap=abs(sum-target);
                    if(gap<min_gap){
                        result=sum;
                        min_gap=gap;
                    }
                    if(sum<target) start++;
                    else end--;
                }
            }
            return result;
        }
    };

  • 0

    We can also remove the duplicate cases like this

          sort(result.begin(), result.end())
    
          result.erase(unique(result.begin(), result.end()), result.end())
    

    The official doc for how to use the above method to remove duplicates is illustrated like this:

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <cctype>
     
    int main() 
    {
        // remove duplicate elements (normal use)
        std::vector<int> v{1,2,3,1,2,3,3,4,5,4,5,6,7};
        std::sort(v.begin(), v.end()); // 1 1 2 2 3 3 3 4 4 5 5 6 7 
        auto last = std::unique(v.begin(), v.end());
        // v now holds {1 2 3 4 5 6 7 x x x x x x}, where 'x' is indeterminate
        v.erase(last, v.end()); 
        for (int i : v)
          std::cout << i << " ";
        std::cout << "\n";
     
        // remove consecutive spaces
        std::string s = "wanna go    to      space?";
        auto end = std::unique(s.begin(), s.end(), [](char l, char r){
            return std::isspace(l) && std::isspace(r) && l == r;
        });
        // s now holds "wanna go to space?xxxxxxxx", where 'x' is indeterminate
        std::cout << std::string(s.begin(), end) << '\n';
    }

Log in to reply
 

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