Divide and conquer can't be used with this problem?Help


  • 0
    W

    I use divide and conquer method, but I can't get accept;
    I get a wrong answer with large test case, so I can't find out what's wrong with me.
    I wish to get help that indicating what's wrong with it, algorithm reason or code reason?

    My code explanation:
    1.I got middle index of array nums with begin index b, end index e;
    2.split the problem to begin index to middle - 1, middle + 1 to end index, including middle index

    public class Solution {
        private int minSubArrayLenR(int b, int e, int[] nums, int s) {
            if(e < b) return 0;
            int m = b + (e - b)/2;
            int lm = b, rm = e;
            int sum = 0;
            int im = Integer.MAX_VALUE;
            for(int i = b;i <= e;i++) {
                sum += nums[i];
            }
            if(sum < s) return 0;
    
            while(sum >= s) {
                im = Math.min(rm - lm + 1, im);
                if(lm < m && rm > m) {
                    if(nums[lm] < nums[rm]) {
                        sum -= nums[lm++];
                    }
                    else if(nums[lm] > nums[rm] ){
                        sum -= nums[rm--];
                    }
                    else {
                        sum -= nums[lm++];
                        sum -= nums[rm--];
                        if(sum < s) {
                            im--;
                        }
                    }
                }
                else if(lm < m) {
                    sum -= nums[lm++];
                }
                else if(rm > m) {
                    sum -= nums[rm--];
                }
                else {
                    break;
                }
            }
            int lr = minSubArrayLenR(b, m - 1, nums, s);
            int rr = minSubArrayLenR(m + 1, e, nums, s);
            return Math.min(im, Math.min(lr==0?Integer.MAX_VALUE:lr, rr==0?Integer.MAX_VALUE:rr));
        }
        //d & c O(nlgn)
        public int minSubArrayLen(int s, int[] nums) {
            if(nums.length == 0) return 0;
            return minSubArrayLenR(0, nums.length - 1, nums, s);
        }
    }
    

Log in to reply
 

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