JAVA two pointer solution 1ms O(n),O(1) and divide and conquer solution 3ms O(nlogn), O(1)


  • 0
    T
       /**
         * two pointers solution with o(1) space complexity;
        */
         public static int minSubArrayLen(int s, int[] nums) {
            int min = 0;
            int left = -1;
            int sum = 0;
            for (int i = 0, j = 0; j < nums.length; j++) {
                if (left == -1) {
                    sum += nums[j];
                    if (sum >= s) {
                        left = sum - s;
                        while (left - nums[i] >= 0) {
                            left -= nums[i ++];
                            if (i == j) return 1;
                        }
                        min =  j - i + 1;
                    }
                }else {
                    left = nums[j] + left;
                    while (left - nums[i] >= 0) {
                        left -= nums[i ++];
                        if (i == j) return 1;
                    }
                    min = Math.min(min, j - i + 1);
                }
            }
            if (left == -1) return 0;
            return min;
        }
    

    the divide and conquer:

     /**
         * divide and conquer n*log(n);
         */
        public int minSubArrayLen(int s, int[] nums) {
            if (nums.length == 0) return 0;
            int res = findMin(s, 0, nums.length-1, nums);
            return res == Integer.MAX_VALUE? 0:res;
        }
    
        private int findMin(int tag, int left, int right, int[] nums) {
            if (left == right) {
                return Integer.MAX_VALUE;
            }
    
            int mid = (left + right)/2;
    
            //divide :
            int l = findMin(tag, left, mid, nums);
            int r = findMin(tag, mid + 1, right, nums);
    
            //conquer:
            return Math.min(findmiddle(left, right, mid, nums, tag),Math.min(l, r));
        }
        /**
         * find the minSize which must contains nums[m] ;
         */
        private int findmiddle(int l, int r, int m, int[] nums, int tag) {
            if (nums[m] >= tag) return 1;
            int min = Integer.MAX_VALUE;
            int left = -1;
            int sum = nums[m];
            int i = m - 1;
            for (; i >= l; i --) {
                sum += nums[i];
                if (sum >= tag) break;
            }
            if (sum >= tag) {
                min = m - i + 1;
                left = sum - tag;
            }
            else i = l;
            for (int j = m + 1; j <= r && i <= m; j++) {
                if (left == -1) {
                    sum += nums[j];
                    if (sum >= tag) {
                        left = sum - tag;
                        while (left - nums[i] >= 0) {
                            left -= nums[i ++];
                            if (i == m ) return j - i + 1;
                        }
                        min =  j - i + 1;
                    }
                }else {
                    left = nums[j] + left;
                    while (left - nums[i] >= 0) {
                        left -= nums[i ++];
                        if (i == m) return Math.min(min, j - i + 1);
                    }
                    min = Math.min(min, j - i + 1);
                }
            }
            if (left == -1) return Integer.MAX_VALUE;
            return min;
        }
    

Log in to reply
 

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