Fast and slow pointer
Remove Duplicates from Sorted Array
26. Remove Duplicates from Sorted Array 删除排序数组中的重复项
Solution: We can use fast and slow pointer technique. Slow pointer matains a subarray which contains non-dupicated array. And fast pointer is used to find duplicated elements.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 0, fast = 0;
int res = 0;
while(fast < nums.length){
// When we find a new element, move forward the slow pointer.
if(nums[slow] != nums[fast]) slow++;
// Let nums[slow] = nums[fast]
nums[slow] = nums[fast];
fast++;
}
return slow+1;
}
}
Move Zeroes
Solution: Dividing the problem into two parts will make it easier. On first stage, like the previous problem, we move all non-zero element to the front of the array. And then, we set all of element of the rest of the array to zero.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0, fast = 0;
// Move non-zero elements
while(fast < nums.length){
if(nums[fast] == 0){
fast++;
} else {
nums[slow] = nums[fast];
slow++;
fast++;
}
}
// Set the rest of the array to zero
while(slow < nums.length){
nums[slow] = 0;
slow++;
}
return;
}
}
Left and right pointer
Binary Search
One of the common appilcations of left and right pointer is binary search. Take 167. Two Sum II - Input Array Is Sorted as an example.
In this problme, we need to find two elements from a sorted array where the sum of these two elements is the given number.
Solution: This is a binary search problem. We can set left pointer pointing to array[0], and right pointer pointing to array[length - 1]. When the sum is less than target, we move the left pointer forward to make the sum larger. When the sum is bigger than target, we move the right pointer backword to make the sum smaller.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
// 题目要求的索引是从 1 开始的
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++; // 让 sum 大一点
} else if (sum > target) {
right--; // 让 sum 小一点
}
}
return new int[]{-1, -1};
}
}
Reverse String
An easy problem, let go through the code directly.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution{
void reverseString(char[] s) {
// Two pointers walk towards each other.
int left = 0, right = s.length - 1;
while (left < right) {
// Swap s[left] and s[right]
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Welcome to reprint, and please indicate the source: Lingjun Meng's Blog Keep the content of the article complete and the above statement information!
