leetcode 209. Minimum Size Subarray Sum | 209. 长度最小的子数组（Java）

心已赠人 2022-10-06 04:50 163阅读 0赞

## 题目 ##

[https://leetcode.com/problems/minimum-size-subarray-sum/][https_leetcode.com_problems_minimum-size-subarray-sum]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

双指针解法，左指针和右指针在合适的时候向右走，并维护一个sum

##### 版本1 #####

思路与版本2相同，循环写的不够优雅

class Solution { 
        public static int minSubArrayLen(int target, int[] nums) { 
            int l = 0;
            int r = 0;
            int sum = nums[0];
            int minLen = Integer.MAX_VALUE;
            while (r < nums.length - 1) { 
                while (sum < target && r < nums.length - 1) { 
                    sum += nums[++r];
                }
                minLen = Math.min(r - l + 1, minLen);
                while (sum >= target && l <= r) { 
                    sum -= nums[l++];
                    if (sum >= target) minLen = Math.min(r - l + 1, minLen);
                }
            }
            if (l == 0 && sum < target) return 0;
            else return minLen;
        }
    }

##### 版本2 #####

Java，和版本1思路相同，实现上比较优雅，效率无差别。改写自官方题解的 C++ 版本。

class Solution { 
        public static int minSubArrayLen(int target, int[] nums) { 
            int left = 0;
            int sum = 0;
            int minLen = Integer.MAX_VALUE;
            for (int i = 0; i < nums.length; i++) { 
                sum += nums[i];
                while (sum >= target) { 
                    minLen = Math.min(i - left + 1, minLen);
                    sum -= nums[left++];
                }
            }
            return minLen != Integer.MAX_VALUE ? minLen : 0;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_minimum-size-subarray-sum]: https://leetcode.com/problems/minimum-size-subarray-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/59ba3def2fc74238b0bc369d079774f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/c0ab13961f2748ae93561d3dab3b02f0.png