LeetCode LintCode和大于S的最小子数组Minimum Size Subarray Sum题目分析

题目

给定一个由 n 个整数组成的数组和一个正整数 s ,请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解,则返回 -1。

样例 给定数组 [2,3,1,2,4,3] 和 s = 7, 子数组 [4,3] 是该条件下的最小长度子数组。

分析

很直观的两根指针的思路。

首先线性时间复杂度的方法,两根指针,类似滑动窗口,指向子数组的头尾,分别更新,遇到大于s就记录j-i,并且将i右移,继续寻找,这样可以找出所有的情况。

代码

public int minSubArrayLen(int s, int[] a) {
  if (a == null || a.length == 0)
    return 0;
  
  int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
  
  while (j < a.length) {
    sum += a[j++];
    
    while (sum >= s) {
      min = Math.min(min, j - i);
      sum -= a[i++];
    }
  }
  
  return min == Integer.MAX_VALUE ? 0 : min;
}

另一种思路,我们会想到如果数组是递增的就好判断了,但这里数组是无序的,我们可以考虑计算前缀数组,那么子数组的和就是前缀数组的差了,利用二分查找

public class Solution {
    /**
     * @param nums: an array of integers
     * @param s: an integer
     * @return: an integer representing the minimum size of subarray
     */
    public int minimumSize(int[] nums, int s) {
        int[] sums = new int[nums.length + 1];
        for (int i = 1; i < sums.length; i++) sums[i] = sums[i - 1] + nums[i - 1];
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < sums.length; i++) {
            int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);
            if (end == sums.length) break;
            if (end - i < minLen) minLen = end - i;
        }
        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }
    
    private int binarySearch(int lo, int hi, int key, int[] sums) {
        while (lo <= hi) {
           int mid = (lo + hi) / 2;
           if (sums[mid] >= key){
               hi = mid - 1;
           } else {
               lo = mid + 1;
           }
        }
        return lo;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

《笨办法学Python》 第4课手记

《笨办法学Python》 第4课手记 这节课目的是让你掌握变量,跟C语言非常类似,很简单。 左边是变量名用”=”号给变量赋值。 不同的是我没有看到变量声明,作者...

1838
来自专栏编程理解

排序算法(五):堆排序

的时间复杂度即可将二叉树重新调整为有序状态。若构造出一种具有特殊节点顺序的二叉树,使得每次对二叉树执行插入或删除节点操作后,都调整保持二叉树根节点的值为树中节...

1412
来自专栏武培轩的专栏

排序算法-插入排序

算法简介 插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应...

2754
来自专栏眯眯眼猫头鹰的小树杈

leetcode 343. Integer Break

这里应用了一个数学的思路。假设我们有一个数字n,该数组可以随机分解为t和n-t。当分解为n/2时可以获得最大的乘积。因此t取n/2时可以得到最好的结果。但是这里...

893
来自专栏专注研发

希尔排序(shell‘ sort)

希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

1003
来自专栏noteless

[三]基础数据类型之Integer详解

2033
来自专栏武培轩的专栏

Leetcode#191. Number of 1 Bits(位1的个数)

编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。

541
来自专栏黑泽君的专栏

java基础学习_集合类02_List的子类、泛型、增强for循环、静态导入、可变参数_day16总结

============================================================================= ==...

671
来自专栏null的专栏

LeetCode——Two Sum

题目: Given an array of integers, find two numbers such that they add up to a spec...

3215
来自专栏Java帮帮-微信公众号-技术文章全总结

HashMap源码分析-jdk1.6和jdk1.8的区别【面试+工作】

在java集合中,HashMap是用来存放一组键值对的数,也就是key-value形式的数据,而在jdk1.6和jdk1.8的实现有所不同。

1442

扫码关注云+社区

领取腾讯云代金券