Fail test case 12, someone can help??


  • 0
    Z

    I use divide & conquer to solve the problem. First try to solve the problem in two subarray. If solved then return the smaller length, else greedily add elements from the middle to the sum.

    It fail test case 12:
    Input:
    697439
    [5334,6299,4199...]
    Output:
    136
    Expected:
    132

    Can someone help me figure out the bug? Thanks in advance.

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int l=find(s, nums, 0, nums.size()-1);
            return l==INT_MAX? 0: l;
        }
        int find(int s, vector<int>& nums, int begin, int end){
            if(begin>end) return INT_MAX;
            if(begin==end) return nums[begin]>=s? 1: INT_MAX;
            int mid=begin+(end-begin)/2; 
            int l1=find(s, nums, begin, mid), l2=find(s, nums, mid+1, end); //search two subarray.
            if(l1!=INT_MAX || l2!=INT_MAX) return min(l1, l2);
            else{ //search from the middle
                int sum=0, i=mid, j=mid+1;
                while(sum<s && i>=0 && j<nums.size()){
                    if(nums[i]>nums[j]) sum+=nums[i--];
                    else sum+=nums[j++];
                }
                while(sum<s && i>=0) sum+=nums[i--];
                while(sum<s && j<nums.size()) sum+=nums[j++];
                return sum<s? INT_MAX: j-i-1;
            }
        }
    };

  • 1
    L
    if(l1!=INT_MAX || l2!=INT_MAX) return min(l1, l2);
    

    You cannot simply return min(l1, l2) if they are not both equal to INT_MAX. What if the best solution is come from the "else" part?

    Should return the minimum of the left, right, and middle part.


  • 0
    Z

    You are right! Thanks. Just not familiar with D&C.


Log in to reply
 

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