Basic features of arrays

Arrays are the simplest data structures.

Arrays are used to store a series of data of the same type. Data is stored consecutively and memory is allocated at one time.

To insert and delete in the middle of an array, all subsequent data must be moved each time to maintain continuity, time complexity O(N).

Array index

Arrays support fast access to data through indexes, an array of length N with subscripts starting at 0 and ending at n-1.

Array elements can be accessed by the array name indexed. The index of the element is placed in square brackets, following the array name.

Array capacity

The array memory space is allocated at a time. During capacity expansion, apply for a larger memory space and copy data to the new memory space. The time complexity is O(N).

Array traversal

for (int i = 0; i < arr.length; I ++) {// use arr[I] to manipulate array elements}Copy the code

485. The maximum number of consecutive 1s

Solution idea 1: counting

The array is iterated and the maximum number of consecutive 1s maxCount and the current number of consecutive 1s curCount are recorded using a counter.

If the current element is 0, update maxCount, the maximum number of consecutive 1s previously recorded, and set curCount, the current number of consecutive 1s, to 0.

Because the last element of the array may be 1, and the longest subarray of consecutive 1s May appear at the end of the array, the current number of consecutive 1s, curCount, needs to be used again to update the maximum number of consecutive 1s, maxCount.

Complexity analysis

Time complexity: O(n) where n is the length of the array. You need to go through the array once. Space complexity: O(1)Copy the code

Animation simulation

The sample

Public static int findMaxConsecutiveOnes(int[] nums) {// maxCount = 0; Int count = 0; for (int i = 0; i < nums.length; If (nums[I] == 0) {// maxCount = max.max (maxCount, count); // count = 0; } else { count++; } } maxCount = Math.max(maxCount, count); return maxCount; }Copy the code

Solution idea 2: sliding Windows

1, specify the window left and right boundaries left, right, maximum continuous number maxCount;

2. Right boundary encounters 1 expansion, right++;

3. If the right boundary is 0, record the window size, that is, the maximum continuous number of current Windows. Update the maximum number of consecutive numbers Max (maxCount, right-left);

4, expand right++, update left = right;

Complexity analysis

Time complexity: O(n) where n is the length of the array. You need to go through the array once. Space complexity: O(1)Copy the code

Animation simulation

The sample

public static int findMaxConsecutiveOnes(int[] nums) { int left = 0; int right = 0; int maxCount = 0; While (right < nums.length){if (nums[right] == 1) {// If the element is 1, the window expands right++; continue; MaxCount = math. Max (maxCount, right-left); maxCount = math. Max (maxCount, right-left); right++; Left = right; } } maxCount = Math.max(maxCount, right - left); return maxCount; }Copy the code

Follow me for more highlights

Welcome to wechat search: Jiongmefeishi (or search: Jiongmefeishi)