[LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和

2021-06-22 11:03

阅读：661

标签：compare vat poi spl subarray coding break als minimal

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn‘t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

这道题的关键是由正整数组成的数组，这样才能保证累加的数组是递增的，才能使用双指针或者二分法。

解法1: 双指针，滑动窗口。

解法2: 二分法

Java: moving window

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
        while (j =s){
                while (sum >= s && i

Java: BS

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i = 1, j = nums.length, min = 0;
        while (i = size) sum -= nums[i - size];
            sum += nums[i];
            if (sum >= s) return true;
        }
        return false;
    }
}

Java: BS　　

public class Solution {
 public int minSubArrayLen(int s, int[] nums) {
        int sum = 0, min = Integer.MAX_VALUE;

        int[] sums = new int[nums.length];
        for (int i = 0; i = s) j = m - 1;
        else i = m + 1;
    }
    return i;
}

Java:

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 = s) {
      min = Math.min(min, j - i);
      sum -= a[i++];
    }
  }
  
  return min == Integer.MAX_VALUE ? 0 : min;
}

Java:

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        return solveNLogN(s, nums);
    }
    
    private int solveN(int s, int[] nums) {
        int start = 0, end = 0, sum = 0, minLen = Integer.MAX_VALUE;
        while (end = s) sum -= nums[start++];
            if (end - start + 1 = key){
               hi = mid - 1;
           } else {
               lo = mid + 1;
           }
        }
        return lo;
    }
}

Python:

# Sliding window solution.
class Solution:
    # @param {integer} s
    # @param {integer[]} nums
    # @return {integer}
    def minSubArrayLen(self, s, nums):
        start = 0
        sum = 0
        min_size = float("inf")
        for i in xrange(len(nums)):
            sum += nums[i]
            while sum >= s:
                min_size = min(min_size, i - start + 1)
                sum -= nums[start]
                start += 1

        return min_size if min_size != float("inf") else 0

Python:　　

# Time:  O(nlogn)
# Space: O(n)
# Binary search solution.
class Solution2:
    # @param {integer} s
    # @param {integer[]} nums
    # @return {integer}
    def minSubArrayLen(self, s, nums):
        min_size = float("inf")
        sum_from_start = [n for n in nums]
        for i in xrange(len(sum_from_start) - 1):
            sum_from_start[i + 1] += sum_from_start[i]
        for i in xrange(len(sum_from_start)):
            end = self.binarySearch(lambda x, y: x

C++:

/ O(n)
class Solution {
public:
    int minSubArrayLen(int s, vector& nums) {
        if (nums.empty()) return 0;
        int left = 0, right = 0, sum = 0, len = nums.size(), res = len + 1;
        while (right = s) {
                res = min(res, right - left);
                sum -= nums[left++];
            }
        }
        return res == len + 1 ? 0 : res;
    }
};

C++:

class Solution {
public:
    int minSubArrayLen(int s, vector& nums) {
        int res = INT_MAX, left = 0, sum = 0;
        for (int i = 0; i = s) {
                res = min(res, i - left + 1);
                sum -= nums[left++];
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

C++: 二分法

// O(nlgn)
class Solution {
public:
    int minSubArrayLen(int s, vector& nums) {
        int len = nums.size(), sums[len + 1] = {0}, res = len + 1;
        for (int i = 1; i  right - i) res = right - i;
        }
        return res == len + 1 ? 0 : res;
    }
    int searchRight(int left, int right, int key, int sums[]) {
        while (left = key) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
};

C++:

class Solution {
public:
    int minSubArrayLen(int s, vector& nums) {
        int res = INT_MAX, n = nums.size();
        vector sums(n + 1, 0);
        for (int i = 1; i

类似题目：

[LeetCode] 53. Maximum Subarray 最大子数组

[LeetCode] 560. Subarray Sum Equals K 子数组和为K

[LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和

标签：compare vat poi spl subarray coding break als minimal

原文地址：https://www.cnblogs.com/lightwindy/p/9678709.html

上一篇：常见前端算法面试题

下一篇：(转)python 判断数据类型

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和
文章链接：http://soscw.com/index.php/essay/97340.html

亲，登录后才可以留言！

[LeetCode] 209. Minimum Size Subarray Sum 最短子数组之和

评论

热门文章

推荐文章

最新文章

置顶文章