week0

Sliding window

suffix sum

Two pointers

1. Two pointers can be used to move/remove/reverse elements in an array or string.
2. Two pointers are an effective technique which is typically used for searching pairs in a sorted arrays.
3. Some single linkedList problems can be easily resolved by two pointers. ...

Examples:

1. Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. [https://leetcode.com/problems/move-zeroes/description/] eg: [0, 1, 0, 3, 12] => [1, 3, 12, 0, 0] We can think like this. For an array [0 0 0 2 1], the first position should be the first non-zeros elements. So we have first pointer to point the position with its value is 0. Another pointer to find the non-zero values. Then swap the values of two pointers. In this case, the first pointer is 0, second point moves to "2". Then swap 0 and 2 to make '2' in the correct position, i.e. [2 0 0 0 1].

void moveZeroes(vector& nums) { for (int zeroIndex = 0, cur = 0; cur < nums.size(); cur++) { if (nums[cur] != 0) { swap(nums[zeroIndex++], nums[cur]); } } }