剑指offer

剑指offer008-和大于等于target的最短子数组

和大于等于target的最短子数组

Posted by 高明 on 2020-01-01

剑指offer008-和大于等于target的最短子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

 

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

 

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

 

进阶：

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

 

注意：本题与主站 209 题相同：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

Related Topics
  • 数组
  • 二分查找
  • 前缀和
  • 滑动窗口

  • 👍 19
  • 👎 0

    • 思路

    思路一

    一开始的想法有一点动态规划的感觉，后面感觉没必要，两个循环，分别计算从i~j的和s，如果s>target，记录一下j-i+1，求最小的距离就好。因为是正整数，所以当s>target的时候，就不需要计算后面的和了，很容易写出代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int res = Integer.MAX_VALUE;

            for (int i = 0; i < nums.length; i++) {
                int s = 0;
                for (int j = i; j < nums.length; j++) {
                    s += nums[j];
                    if (s >= target) {
                        res = Math.min(j - i + 1, res);
                        break;
                    }
                }
            }
            return res == Integer.MAX_VALUE ? 0 : res;
        }
    }

    思路二

    这种连续数组应该想到双指针，左右指针都指向开始的位置即left = right = 0，初始和为nums[0]

    每次计算的时候，如果求和s<target，right++，如果求和s>=target，left++，并且记录当时的下标值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int left = 0;
            int right = 0;
            int s = nums[0];
            int res = Integer.MAX_VALUE;
            while (right < nums.length) {
                if (s < target) {
                    right += 1;
                    if (right < nums.length) {
                        s += nums[right];
                    }

                } else {
                    s -= nums[left];
                    res = Math.min(res, right - left + 1);
                    left += 1;
                }
            }
            return res == Integer.MAX_VALUE ? 0 : res;
        }
    }

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int res = Integer.MAX_VALUE;

            for (int i = 0; i < nums.length; i++) {
                int s = 0;
                for (int j = i; j < nums.length; j++) {
                    s += nums[j];
                    if (s >= target) {
                        res = Math.min(j - i + 1, res);
                        break;
                    }
                }
            }
            return res == Integer.MAX_VALUE ? 0 : res;
        }
    }
    1
    2
    3
    解答成功:
    执行耗时:135 ms,击败了5.93% 的Java用户
    内存消耗:38.4 MB,击败了42.34% 的Java用户
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int left = 0;
            int right = 0;
            int s = nums[0];
            int res = Integer.MAX_VALUE;
            while (right < nums.length) {
                if (s < target) {
                    right += 1;
                    if (right < nums.length) {
                        s += nums[right];
                    }

                } else {
                    s -= nums[left];
                    res = Math.min(res, right - left + 1);
                    left += 1;
                }
            }
            return res == Integer.MAX_VALUE ? 0 : res;
        }
    }
    1
    2
    3
    解答成功:
    执行耗时:1 ms,击败了99.82% 的Java用户
    内存消耗:38.5 MB,击败了18.45% 的Java用户
    FEATURED TAGS
    剑指offer
    FRIENDS