21 lines, 56 ms in C++


  • 2
    J
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> ans;
            if(nums.size() < 3) return ans;
            sort(nums.begin(), nums.end());
            for(int i = 0; i < nums.size() - 2; i ++) {
                // in case of duplicate solutions
                if(i > 0 && nums[i] == nums[i-1]) continue;
                int a = nums[i];
                int lf = i + 1;
                int rt = nums.size() - 1;
                while(lf < rt) {
                    int b = nums[lf];
                    int c = nums[rt];
                    if(0 == a + b + c) {
                        ans.push_back(vector<int> {a, b, c});
                        // in case of duplicate solutions
                        while(lf < nums.size() && nums[lf] == b) lf ++;
                        // in case of duplicate solutions
                        while(rt >= 0 && nums[rt] == c) rt --;
                    }
                    else if(a + b + c > 0) rt --;
                    else lf ++;
                }
            }
            return ans;
        }
    };

  • 0
    S

    @johnsondu Thank you so much, I couldn't think of any n^2 solution, the ones used with mutlimaps failed because time limit exceeded though the answers were right.Can you please elaborate on why this solution works ? especially the last two conditions

    else if(a + b + c > 0) rt --;
                    else lf ++;
    

    from what i understood I think that if the final sum > 0 we need to move backwards in order to get a lesser number to make the final sum as 0 and the reverse if sum<0. Correct me if I am wrong.

    Here is my code using multimaps, please let me kow if you can make any optimizations on this.

    class Solution {
    public:
    
    	vector<vector<int>> threeSum(vector<int>& nums) {
    		sort(nums.begin(), nums.end());
    		set<vector<int>> s;
    		multimap<int, int> dict;
    		for (auto i = 0; i<nums.size(); i++) {
    			dict.insert(std::pair<int, int>(nums[i], i));
    		}
    
    		vector<int> res;
    		vector<vector<int>> result;
    
    		for (int i = 0; i < nums.size(); i++) {
    			if (i>0 && nums[i] == nums[i - 1])
    				continue;
    			int sum = -nums[i];
    			for (int j = i + 1; j < nums.size(); j++) {
    				int x = sum - nums[j];
    				if (x<nums[0] || x>nums[nums.size() - 1])
    					continue;
    
    				if (dict.find(x) != dict.end() && dict.find(x)->second != j && dict.find(x)->second != i)
    				{
    					res = { -sum,nums[j],x };
    					sort(res.begin(), res.end());
    					if (s.find(res) == s.end()) {
    						result.push_back(res);
    						s.insert(res);
    					}
    					res.clear();
    				}
    			
    			}
    		}
    		return result;
    	}
    };
    

  • 0
    J

    @sujiths52 just like you say, when a + b + c > 0, since a < b < c, then what we do in this case is deduce c, since a is fixed and b is smallest, and reverse is sum < 0. your code time complexity is O(n^2 logn), since find in map time complexity is O(log n), I suggest to you that may be use unordered_map<int, vector<int>> to store the original data information, where vector<int> store the int's subscripts. then complexity will be O(n^2)


Log in to reply
 

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