Arrays and strings

[YuezhenQin]

Overview

1. Two Pointers (双指针): two pointers refers to using two integer variables to move along some iterables.
2. Sliding Window (滑动窗口)
3. Prefix Sum (前缀结合)

[YuezhenQin]

Two pointers: two pointers refers to using two integer variables to move along some iterables.

1. left, right: Move left and right towards each other until they meet. Example: isPalindrome(str) ; reverse(chars);

2. i, j: Moved two pointers along two different inputs simultaneously until all elements have been checked. Example: merge(arr1, arr2); isSubsequence(str1, str2);

[YuezhenQin]

Sliding Window: Dynamic and Fixed Sliding Window

Sliding window: as we add and remove elements, we are "sliding" our window along the input from left to right. The window's size is constantly changing: right - left + 1.

Remember, the idea of a sliding window is to add elements by sliding to the right until the window violates the constraint. Once it does, we shrink the window from the left until it no longer violates the constraint.

Example: 1.given an array and k, find the length of the longest subarray whose sum is less than or equal to k. 2.given a binary string, find is the longest substring that contains at most one "0". 3.given an array and k, find the number of subarrays where the product of all the elements in the subarray is strictly less than k.

In the examples we looked at above, our window size was dynamic. Sometimes, a problem will specify a fixed length k.

As we mentioned before, we can build a window of length k and then slide it along the array. Add and remove one element at a time to make sure the window stays size k. If we are adding the value at i, then we need to remove the value at i - k. The total number of sliding windows is arr.length - k + 1.

[YuezhenQin]

Like two pointers, sliding windows work the same with arrays and strings - the important thing is that they're iterables with ordered elements. It is actually implemented using two pointers! Before we start, we need to talk about the concept of a subarray: Given an array, a subarray is a contiguous section of the array.

[YuezhenQin]

A subarray can be defined by two indices, the start and end. Let's call the starting index the left bound and the ending index the right bound. Another name for subarray in this context is "window".

[YuezhenQin]

When should we use sliding window?

• First, the problem will either explicitly or implicitly define a condition that make a subarray "valid". There are 2 components regarding what makes a subarray valid:

  • A constraint metric. It could be the sum, the product, contains the certain number of unique elements, the frequency of a specific element, or any other attribute.
  • A numeric restriction on the constraint metric. This is what the constraint metric should be for a subarray to be considered valid.

• Second, the problem will ask you to find valid subarrays in some way.

  • The most common task you will see is finding the best valid subarray. The problem will define what makes a subarray better than another.

  • Another common task is finding the number of valid subarrays.

[YuezhenQin]

Why is sliding window efficient?

For any array, how many subarrays are there? If the array has a length of n, there are n subarrays of length 1. Then there are n - 1 subarrays of length 2 (every index except the last one can be a starting index), n - 2 subarrays of length 3 and so on until there is only 1 subarray of length n. $$\sum_{k=1}^nk=\frac{n(1+n)}{2}$$

[YuezhenQin]

Prefix Sum 前缀结合

1.1 定义

Prefix sum: create an array, prefix[], where prefix[i] is the sum of all elements up to the index i.

1.2 计算方法

S_i = S_i-1 + a[i]

1.3 如何使用

For 1D array, the sum of the subarray from i to j, the answer is prefix[j] - prefix[i - 1], or prefix[j] - prefix[i] + nums[I]. For 2D array, ...

1.4 效果

It only costs O(n) to build but allows all future subarray queries to be O(1), so it can usually improve an algorithm's time complexity by a factor of O(n), where n is the length of the array.

1.5 Leetcode 练习

Solution523 Solution1292

1.6 Reference

[1] Introduction to Prefix Sum, USACO Guide

[YuezhenQin]

字符串相关问题

1.分解字符串: String.substring() 2.遍历字符串中的所有字符

• for (int i = 0; i < str.length(); I++) {char c = str.charAt(i);}
• for (char c: str.toCharArray()) {} 3.合并字符串: 使用字符串拼接操作符 “+” 或直接使用 StringBuilder 4.逆转字符串 new StringBuilder(str).reverse() 5.去掉字符串末尾的空白符 String.trim() 6.大小写控制 String.toLowerCase()/toUpperCase()

[YuezhenQin]

Arrays.toString() Arrays.stream(arr).max().getAsInt();