# The title

portal

## The text

Given an array A of zeros and ones, we can change up to K values from 0 to 1.

Returns the length of the longest (continuous) subarray containing only 1.

Example 1:

Input: A = [1,1,1,0,0, 1,1,1,0], K = 2

Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1] The bold digit is flipped from 0 to 1, and the longest subarray length is 6.

Example 2:

Input: A =,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1 [0], K = 3

Output: 10:,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1 [0] bold digital flip from 0 to 1, the longest length of the subarray to 10.

Tip:

``1 <= a. length <= 20000 0 <= K <= A.length A[I] is 0 or 1Copy the code``

Source: LeetCode

## The template

``int longestOnes(int* A, int ASize, int K){}Copy the code``

# The problem solving

## Analysis of the

One of the characteristics of array elements is that there are only two types of elements, 0 and 1, and there is a certain inclusive size of K for 0, so I think we can use the sliding window to solve this problem, and we want to return the length of the largest window traversed to the end. For the head pointer, we leave this the same, except that the miscellaneous pointer indicates that we count when 0 is detected. When the count reaches a certain length, we return the head pointer to the position where 0 was first detected so that the traversal continues until the end of the traversal

### Initialize data

Right is no longer defined here but is defined within the loop

``````    int left = 0, lc = 0, rc = 0;// The corresponding left pointer, left count, right count
int len = 0;// The final length returned by the program
Copy the code``````

### Traversal cycle

The right pointer moves from 0 to asize-1

``````for (int right = 0; right < ASize; ++right) {

}
Copy the code``````

### Counting rule

The right count counts the number of zeros traversed by the right pointer, so we can use 1-a [right] to determine if it is 0, and if it is, we add 1 to the count.

``````rc =rc + 1 - A[right];
Copy the code``````

Left counting same thing

``````lc =lc + 1 - A[left];
Copy the code``````

Then the problem comes. In the loop, the right pointer keeps moving backward, and if the left pointer does not move, it will not proceed. Analysis shows that only when the right pointer traverses k or more zeros will the left pointer move behind the first zero, and the movement of the left pointer also needs to be defined, so there are

`````` while (lc < rc - K) {
lc =lc + 1 - A[left];
++left;
}
Copy the code``````

### Calculate the length of the

The length must be taken using fmax, and it needs to be updated in the loop, while the left side is constantly decreasing as it decreases, so it might as well go to the left side of the circular pointer movement, put it in the right side of the loop. The real length is the right pointer minus the left pointer plus 1. And then I’m going to take len and I’m going to take len.

``````len = fmax(len, right - left + 1);
Copy the code``````

## Complete source code

``````int longestOnes(int* A, int ASize, int K) {
int left = 0, lc = 0, rc = 0;
int len = 0;
for (int right = 0; right < ASize; ++right) {
rc =rc + 1 - A[right];
while (lc < rc - K) {
lc =lc + 1 - A[left];
++left;
}
len = fmax(len, right - left + 1);
}
return len;
}

Copy the code``````

### Running effect

Fortunately, it’s the same as the official solution