Look at leetcode

Given an array containing n positive integers and a positive integer target.

Find out the continuous sub array [numsl, numsl+1,..., numsr-1, numsr] with the smallest length satisfying its sum ≥ target in the array, and return its length. If there is no eligible subarray, 0 is returned.
Example 1:
Input: target = 7, Num = [2,3,1,2,4,3]
Output: 2
Explanation: subarray [4,3] is the subarray with the smallest length under this condition.
Source: LeetCode
Link: https://leetcode-cn.com/problems/minimum-size-subarray-sum
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

The problem can be solved by prefix and + binary search, with a time complexity of O ( n l o g n ) O(nlogn) O(nlogn).
answer:

public class PrefixSum {
    public static void main(String[] args) {
        //Given a sequence of positive integers
        int[] nums=new int[]{1,1,1,1,1,1,1,1};
        PrefixSum prefixSum = new PrefixSum();
        System.out.println(prefixSum.minSubArrayLen(nums,11));
    }
    public int  minSubArrayLen(int[] nums, int target){
        int[] sums=Sum(nums);
        int sumsMin=Integer.MAX_VALUE;
        for(int i=0;i<sums.length;i++){
            int tar=sums[i]+target;
            int boundary=binarySearch(sums,tar);
            if(boundary>0) {
                sumsMin = Math.min(sumsMin, boundary - i);
            }
        }

       return  sumsMin==Integer.MAX_VALUE?0:sumsMin;
    }
    //  Find the prefix sum, which is in ascending order
    public int[] Sum(int[] nums){
        int sum=0;
        int[] sums=new int[nums.length+1];
        sums[0]=0;
        //Use one traversal to find the prefix and sum of array nums, where sum [i] represents the sum of nums[0] to nums[i-1]
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
            sums[i+1]=sum;
        }
        return sums;
    }
    //The premise is to ensure that the array is in ascending order
    //Use bisection to find the first > = sums [i] + target element in the prefix and
    public int binarySearch(int[] sums,int tar){
        int left=0;
        int right=sums.length-1;
        if(sums[right]>=tar) {
            while (left < right) {
                int mid = left + (right - left) / 2;//The final mid is always equal to left
                if (sums[mid] < tar) {//Finally, the judgment is true, left==right, and the result is returned
                    left = mid + 1;
                } else {
                    right = mid;//Place the subscript of > = target on the right boundary, which is the result at the end
                }
            }
            return left;
        }
        return -1;
    }
}

Binary search

1. 1. 1. Premise of binary search: the array is required to be an ordered array, generally in ascending order; Duplicate elements are allowed in the array;
2. 2. 2. The dichotomy has three pointers: l e f t left left, r i g h t right right, m i d mid mid, as the name suggests;
3. 3. 3. The last cycle, l e f t + 1 = = r i g h t left+1==right left+1==right; m i d = = l e f t mid==left mid==left; r i g h t right right always captures qualified elements; The final return is r i g h t right right；
2. 2. 2. Binary search code:

public int binarySearch(int[] sums,int tar){
        int left=0;
        int right=sums.length-1;
        if(sums[right]>=tar) {
            while (left < right) {
                int mid = left + (right - left) / 2;//The final mid is always equal to left
                if (sums[mid] < tar) {//Finally, the judgment is true, left==right, and the result is returned
                    left = mid + 1;
                } else {
                    right = mid;//Place the subscript of > = target on the right boundary, which is the result at the end
                }
            }
            return left;
        }
        return -1;
    }

The above code can find a given array s u m s sums First in sums > = >= >=Given number t a r tar tar element and returns the array index when there is no > = >= >=Given number t a r tar Return - 1 when the element of tar;

Source code analysis

1. 1. 1. The source code is one more than the above code. It returns the position of an element that does not exist in the array in the form of negation, which is in the first position > = >= >=Given number t a r tar The adjacent left side of the tar element;

private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

If there is no target element in the array, the element position of the first > target element is returned. This position is returned in the form of inverse number: - (low+1) it is low after negation

Feeling: I feel that the elements of the array given by leetcode can be natural numbers, that is, there can be elements with 0.