长度最小的子数组

长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //通过双指针
        int res=Integer.MAX_VALUE;
        int sum=0;
        for(int i=0,j=0;i<nums.length;i++){
            sum+=nums[i];
            while(sum>=target){
                res=Math.min(res,i-j+1);
                sum-=nums[j++];
            }
        }
        return res==Integer.MAX_VALUE? 0:res;
    }
}

滑动窗口变形 将x减到0的最小操作数

将x减到0的最小操作数
dfs超时

class Solution {
    int res=Integer.MAX_VALUE;
    public int minOperations(int[] nums, int x) {
        dfs(nums,0,nums.length-1,x,0);
        return res==Integer.MAX_VALUE? -1:res;
    }

    public void dfs(int[] nums,int left,int right,int x,int cnt){
        if(x==0){
            res=Math.min(res,cnt);
            return;
        }
        if(x<0||left>right){
            return;
        }
        if(x>0&&left<=right){
            dfs(nums,left+1,right,x-nums[left],cnt+1);
            dfs(nums,left,right-1,x-nums[right],cnt+1);
        }
    }

}

等价于最长子数组使得该子数组和为sum-x

class Solution {
    public int minOperations(int[] nums, int x) {
        int sum=0;
        int n=nums.length;
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        int target=sum-x;
        if(target<0){
            return -1;
        }
        if(target==0){
            return n;
        }
        int s=0;
        int len=-1;
        for(int i=0,j=0;i<n;i++){   
            s+=nums[i];
            while(s>target){
                s-=nums[j++];
            }
            if(s==target){//先移动左边的指针j,然后判断是否满足条件子数组
                len=Math.max(len,i-j+1);
            }
        }
        if(len==-1){
            return -1;
        }else{
            return n-len;
        }
    }
}