WA in oj 308/311 test case, but right in local machine.


  • 0
    H

    My method is easy to unsatnd, it is like the two sum.
    firstly,i sorted the nums.
    secondly,choose tag form (1,....length()-1-1);
    let tag split the nums into two parts , if the nums[low]+nums[tag]+nums[high]==0,the smallest one must be in the left part(0,tag-2),the bigger one must be in the right part(tag,length()-1).

    vector<vector<int> > threeSum(vector<int> nums) {
    	vector<vector<int> > res;
    	if(nums.size()<3) return res;
    	sort(nums.begin(),nums.end());
    	int low=2,high=1;
    	for (int tag = 1; tag < nums.size()-1; tag++)
    	{
    		if(tag==1 || nums[tag]!=nums[tag-1]) {
    			low=0;
    			high=nums.size()-1;
    		}
    		while(low < tag && high > tag){
    			// cout<<low<<","<<high<<endl;
    			int numberToFind = 0-nums[tag];
    			if(nums[low]+nums[high] < numberToFind) low++;
    			else if(nums[low]+nums[high] > numberToFind) high--;
    			else{
    				vector<int> temp(3,0);
    				temp[0]=nums[low];
    				temp[1]=nums[tag];
    				temp[2]=nums[high];
    				res.push_back(temp);
    				while(nums[low]==nums[low+1])  low++;
    				while(nums[high]==nums[high+1])  high--;
    				low++;
    				high--;
    			}
    		}
    	}
    	sort(res.begin(),res.end()) ;
    	return res;
    }
    

    the paoblem is: in my laptop it works fine and right, but in the oj,it was WA in the 308/311 or 310/311 test case.
    It is very strange! i took the whole day to deal with problem,but i can't figure out it.
    if someone can help me test the code in his/her machine,it may be help me a lot.
    BTW i use the g++ (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4


  • 0
    A

    Try :

    vector<int> nums(3,0);
    nums[0] = (numeric_limits<int>::min)();
    nums[1] = (numeric_limits<int>::min)();
    nums[2] = 0;
    

    I rewrite your code and returns WA in 310/311 test case

    vector<vector<int> > threeSum(vector<int> nums) {
        vector<vector<int> > res;
        if(nums.size()<3) return res;
        sort(nums.begin(),nums.end());
        int low=2,high=1;
        for (int tag = 1; tag < nums.size()-1; tag++)
        {
            if(tag==1 || nums[tag]!=nums[tag-1]) {
                low=0;
                high=nums.size()-1;
            }
            while(low < tag && high > tag){
                long long numberToFind = 0-(long long)nums[tag];
                if(nums[low]+nums[high] < numberToFind) low++;
                else if(nums[low]+nums[high] > numberToFind) high--;
                else{
                    vector<int> temp(3,0);
                    temp[0]=nums[low];
                    temp[1]=nums[tag];
                    temp[2]=nums[high];
                    res.push_back(temp);
                    while(nums[low]==nums[low+1])  low++;
                    while(nums[high]==nums[high+1])  high--;
                    low++;
                    high--;
                }
            }
        }
        sort(res.begin(),res.end()) ;
        return res;
    } 

  • 0
    H

    I only seen you changed the 'int' to 'long long' ,right?
    It's WA in the last test case , also makes confused.


Log in to reply
 

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