Looking for more efficient solution, mine is O(n^3)


  • 0
    D
    class Solution 
    {
    public:
    	vector<vector<int> > fourSum(vector<int> &num, int target) 
    	{
    		vector<vector<int>> resultSet;
    		int n = num.size();
    		if (n < 4)
    		{
    			return resultSet;
    		}
    
    		sort(num.begin(), num.end());
    		
    		vector<int> result(4);
    		for (int dIndex = n - 1; dIndex >= 3; dIndex--)
    		{
    			if ((dIndex < (n - 1)) && (num[dIndex + 1] == num[dIndex]))
    			{
    				continue;
    			}
    
    			result[3] = num[dIndex];
    
    			for (int cIndex = dIndex - 1; cIndex >= 2; cIndex--)
    			{
    				if ((cIndex < (dIndex - 1)) && (num[cIndex + 1] == num[cIndex]))
    				{
    					continue;
    				}
    
    				int threeSum = target - num[dIndex] - num[cIndex];
    				result[2] = num[cIndex];
    				int start = 0;
    				int end = cIndex - 1;
    				while (start < end)
    				{
    					int curSum = num[start] + num[end];
    					if (curSum == threeSum)
    					{
    						result[0] = num[start];
    						result[1] = num[end];
    						resultSet.push_back(result);
    						do
    						{
    							start++;
    							end--;
    						} while (start < end && num[start] == num[start - 1] && num[end] == num[end + 1]);
    					}
    					else if (curSum > threeSum)
    					{
    						end--;
    					}
    					else
    					{
    						start++;
    					}
    				}
    			}
    		}
    
    		return resultSet;
    	}
    };

  • 0
    A

    we can get O( 4 * n * target ) by using dynamic programming


  • 0
    D

    Thanks for you reply. Your solution sounds great, but what if target is negative or too large. And I'm wondering how can DP be applied here. It will be appreciated if you can give more details


  • 0
    A

    yeah, it is actually a problem need to focus in. A method is to add the minimum to all the value. Every algorithm has its suit occation, the dp method is suit for the value is not large but the "n" is large.Exactly when n * n > target value, dp method is faster.


  • 0
    Z

    Hi aqin, I was thinking dp before but then I give up. How could you define your dp array to store any possible subsum value, I mean assume target is 3, it is possible to have -2, 10 or any other value in sum of any two or three numbers. If you indeed found a dp accepted solution, could you post it for reference? Thank you in advanced!


  • 0
    A

    if ( dp[ n - 1 ][ target - val[ n ] ][ num - 1 ] == 1 ) dp[ n ][ target ][ num ] = 1 and pre[ target ][ num ].push_back( val[ n ] ); then you can use the pre to get all the solution


  • 0
    Z

    Yes, I know the recursion but in your example, the possible value of the second index--(target-var[n]) can be any possible values since the target changes as well every time you added one number in this solution.For clarify, let me assume num=[3,1,-1],target=0 then the target-var[n] can be 0-3, 0-1,0-(-1),0-1-3,0-1+1,0-3+1. So for first declare the array dp, how do you know the size of second index before compute all possible subsum? Thanks for you reply!!


  • 0
    A

    I am sorry but if you notice the comment i reply to Deo , i mean the negtive number is not allowed for the "dp". So you can add the minimum value to all the value to avoid this case.of course, the target would be 4 * minimum larger


  • 0
    Z

    Oh, ok. I see this time. Thanks so much for instant reply!:D


  • 0
    A

    :D, you are welcome


Log in to reply
 

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