18 lines concise and easy understand C++ solution


  • 2
    A

    This Solution is n^2

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

    This solution is n^2*logn

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> res;
            if(nums.size() < 3) return res;
            sort(nums.begin(), nums.end());
            for(int i = 0; i < nums.size() - 2; i++){
                if(i >= 1 && nums[i] == nums[i - 1]) continue;
                for(int j = i + 1; j < nums.size() - 1; j++){
                    if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                    int target = 0 - nums[i] - nums[j];
                    int l = j + 1, r = nums.size() - 1;
                    while(l <= r){
                        int mid = l + (r - l)/2;
                        if(nums[mid] == target){
                            vector<int> tmp = {nums[i], nums[j], nums[mid]};
                            res.push_back(tmp);
                            break;
                        }else if(nums[mid] > target) r = mid - 1;
                        else l = mid + 1;
                    }
                }
            }
            return res;
        }
    };
    

    Both solutions are accepted ~


  • 0
    S

    while((r < nums.size() - 2 && nums[r] == nums[r + 1]) || r == i) r--;

    shoud be :

    while((r < nums.size() - 1 && nums[r] == nums[r + 1]) || r == i) r--;


  • 0
    A

    Yeah, you are right, THX~~


  • 0
    B

    while((r < nums.size() - 1 && nums[r] == nums[r + 1]) || r == i) r--;
    while((l > i + 1 && nums[l] == nums[l - 1]) || l == i) l++;
    what is the function of (r == i) and (l == i)? my answer is:
    while(l<r && l>i+1 && nums[l] == nums[l-1]) l++;
    while(l<r && r<nums.size() - 1 && nums[r] == nums[r+1]) r--;


Log in to reply
 

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