通过快慢指针，每次先让快指针移动，完成操作后慢指针++，如此重复。
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0, fast = 0;
while (fast < nums.length) {
if(nums[fast] != 0) {
nums[slow++] = nums[fast];
}
fast++;
}
while (slow < nums.length) {
nums[slow++] = 0;
}
}
}
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 0, fast = 0;
while (fast < nums.length) {
if(nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
fast++;
}
return slow + 1;
}
}
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0, fast = 0;
while (fast < nums.length) {
if(nums[fast] != val) {
nums[slow++] = nums[fast];
}
fast++;
}
return slow;
}
}
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null) {
if(fast.val == slow.val) {
slow.next = fast.next;
}else {
slow = slow.next;
}
fast = fast.next;
}
return head;
}
}
双指针法 O(n)
class Solution {
public int[] twoSum(int[] numbers, int target) { //题目数组要求下标从1开始
int left = 0, right = numbers.length - 1;
while (left < right) {
if(numbers[left] + numbers[right] == target) {
return new int[] {left + 1, right + 1};
}else if(numbers[left] + numbers[right] > target){
right--;
}else{
left++;
}
}
return new int[] {left + 1, right + 1};
}
}
双指针+二分 best:O(logn) worst:O(n)
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (numbers[left] + numbers[mid] > target) { //如果中间都超过，则 right = mid - 1
right = mid - 1;
} else if (numbers[mid] + numbers[right] < target) { //如果中间都不够，则 left = mid + 1
left = mid + 1;
} else if (numbers[left] + numbers[right] > target) {
right--;
} else if (numbers[left] + numbers[right] < target) {
left++;
} else {
return new int[] {left + 1, right + 1};
}
}
return null;
}
}
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
}
}
}
从中间向两端双指针：对于奇数和偶数都适用。时间:O(n²) 空间:O(1)
给定如下函数，若 l == r 找奇数回文串，若 l、r 相邻则寻找偶数回文串。
String palindrome(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--; r++;
}
return s.substring(l + 1, r);
}
完整代码
class Solution {
public String longestPalindrome(String s) {
String res = "";
for(int i = 0; i < s.length(); i++) {
String s1 = palindrome(s, i, i);
String s2 = palindrome(s, i, i + 1);
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
public String palindrome(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return s.substring(l + 1, r);
}
}
(有空记得看)Manacher's Algorithm 马拉车算法。时间:O(n) 空间:O(n)
双指针：由于#只影响前面的字母，所以可以逆向处理。
每次处理 s 和 t 是否存在#，并改变对应指针位置，知道遇到字母再去比较字母是否一样。
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
int skipi = 0, skipj = 0;
while(i >= 0 || j >= 0) {
while(i >= 0) {
if(s.charAt(i) == '#') {
skipi++;
i--;
}else if(skipi > 0) {
skipi--; // 不能直接 i -= skipi。∵存在连续两个## + 一个字母 的情况
i--;
}else break;
}
while(j >= 0) {
if(t.charAt(j) == '#') {
skipj++;
j--;
}else if(skipj > 0) {
skipj--;
j--;
}else break;
}
if(i >= 0 && j >= 0) {
if(s.charAt(i) != t.charAt(j)) {
return false;
}
}else{
if(i >= 0 || j >= 0) {
return false;
}
}
i--;
j--;
}
return true;
}
}
依旧使用双指针，比较两端平方数哪个更大。
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0, right = nums.length - 1;
int[] ans = new int[nums.length];
int count = nums.length;
while (left <= right) {
int a = nums[left] * nums[left];
int b = nums[right] * nums[right];
if(a <= b) {
ans[--count] = b;
--right;
}else {
ans[--count] = a;
++left;
}
}
return ans;
}
}
