LeetCode题解209.minimum-size-subarray-sum

题目地址

https://leetcode.com/problems/minimum-size-subarray-sum/description/

题目描述

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).

思路

用滑动窗口来记录序列， 每当滑动窗口中的 sum 超过 s， 就去更新最小值，并根据先进先出的原则更新滑动窗口，直至 sum 刚好小于 s

这道题目和 leetcode 3 号题目有点像，都可以用滑动窗口的思路来解决

关键点

• 滑动窗口简化操作(滑窗口适合用于求解这种要求连续的题目)

代码

• 语言支持：JS，C++

JavaScript Code：

/*
 * @lc app=leetcode id=209 lang=javascript
 *
 * [209] Minimum Size Subarray Sum
 *
 */
/**
 * @param {number} s
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(s, nums) {
  if (nums.length === 0) return 0;
  const slideWindow = [];
  let acc = 0;
  let min = null;

  for (let i = 0; i < nums.length + 1; i++) {
    const num = nums[i];

    while (acc >= s) {
      if (min === null || slideWindow.length < min) {
        min = slideWindow.length;
      }
      acc = acc - slideWindow.shift();
    }

    slideWindow.push(num);

    acc = slideWindow.reduce((a, b) => a + b, 0);
  }

  return min || 0;
};

C++ Code：

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int num_len= nums.size();
        int left=0, right=0, total=0, min_len= num_len+1;
        while (right < num_len) {
            do {
                total += nums[right++];
            } while (right < num_len && total < s);
            while (left < right && total - nums[left] >= s) total -= nums[left++];
            if (total >=s && min_len > right - left)
                min_len = right- left;
        }
        return min_len <= num_len ? min_len: 0;
    }
};

扩展

如果题目要求是 sum = s, 而不是 sum >= s 呢？

eg:

var minSubArrayLen = function(s, nums) {
  if (nums.length === 0) return 0;
  const slideWindow = [];
  let acc = 0;
  let min = null;

  for (let i = 0; i < nums.length + 1; i++) {
    const num = nums[i];

    while (acc > s) {
      acc = acc - slideWindow.shift();
    }
    if (acc === s) {
      if (min === null || slideWindow.length < min) {
        min = slideWindow.length;
      }
      slideWindow.shift();
    }

    slideWindow.push(num);

    acc = slideWindow.reduce((a, b) => a + b, 0);
  }

  return min || 0;
};

LeetCode题解1186.maximum-subarray-sum-with-one-deletion

题目地址 https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/ 题目描述 给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。 换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦）…

LeetCode题解1879. Two Sum VII

给定一个已经 按绝对值升序排列 的数组，找到两个数使他们加起来的和等于特定数。函数应该返回这两个数的下标，index1必须小于index2。注意返回的值是0-based。请使用双指针完成本题，否则你有可能会被取消比赛资格。注意事项:```- 数据保证nums中的所有数的互不相同的。- nums数组长度≤100000- nums内的数≤1000000000``…

LeetCode题解152.maximum-product-subarray

题目地址 https://leetcode.com/problems/maximum-product-subarray/description/ 题目描述 Given an integer array nums, find the contiguous subarray within an array (containing at least one num…

LeetCode题解113.path-sum-ii

题目地址 https://leetcode.com/problems/path-sum-ii/description/ 题目描述 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum. Note: A leaf…

LeetCode题解15.3-sum

题目地址 https://leetcode.com/problems/3sum/description/ 题目描述 Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in…