The title

Let’s start with a leetcode algorithm title to introduce this algorithm. The title link is209:

Violent solution

The violent solution to this problem is, of course, two for loops, and then you keep looking for subsequences that fit, and of course, the time complexity is obviously O(n^2).

code

class Solution { public int minSubArrayLen(int target, int[] nums) { int result = Integer.MAX_VALUE; Int sum = 0; Int subLength = 0; For (int I = 0; i < nums.length; I ++) {// set the start of the subsequence to I sum = 0; for (int j = i; j < nums.length; J ++) {// Set the subsequence terminating position to j sum += nums[j]; If (sum >= target) {if (sum >= target) {result subLength = j-i + 1; Result = result < subLength? result : subLength; break; Return result == integer.max_value? Return result == integer.max_value? 0 : result; }}Copy the code

The complexity of the

  • Time complexity: O(n^2)
  • Space complexity: O(1)

Sliding window algorithm

The sliding window algorithm, in fact, constantly adjusts the starting position and ending position of the sub-sequence, so as to obtain the desired result. Take this topic as an example:

In the process of moving the two Pointers before and after, the following Windows that meet the conditions will be found: [2,3,1,2], [3,1,2,4], [1,2,4], [2,4,3] finally [4,3] is the optimal solution that meets the problem solving conditions

Sliding Windows can also be understood as a double pointer method! However, this solution is more like a window movement, so it is better called sliding window.

In this case, the following three points are determined to achieve sliding Windows:

  • What’s in the window?
  • How do I move the starting position of the window?
  • How do I move the end of a window?

A window is the smallest contiguous subarray whose sum is ≥ s. How to move the starting position of the window: If the value of the current window is greater than s, the window will move forward (that is, shrink). How to move the end position of the window: The end position of the window is the pointer to iterate over the array. The start position of the window is set to the start position of the array. The key to solve the problem is how to move the starting position of the window, as shown in the figure:

The difficulty and essence of sliding window lies in how to move the two Pointers after finding a window that meets the conditions:

While (sum >= target) {subLength = math. min(subLength, right-left + 1); Sum -= array[left++]; }}Copy the code

The complete code

class Solution { public int minSubArrayLen(int target, int[] array) { int length = array.length; int subLength = length + 1; int sum = 0; int left = 0; for (int right = 0; right < length; right++) { sum += array[right]; while (sum >= target) { subLength = Math.min(subLength, right - left + 1); sum -= array[left++]; } } return subLength > length ? 0 : subLength; }}Copy the code

The complexity of the

  • Time complexity: O(n)
  • Space complexity: O(1)

【 reference 】 【1】github.com/youngyangya…

This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.