数组篇：双指针技巧
# 数组篇：双指针技巧
# 一、快慢指针
# 26. 删除有序数组中的重复项 (opens new window)
☀️☀️☀️☀️☀️☀️题解一：
class Solution {
public int removeDuplicates(int[] nums) {
int slow=0,fast=0;
while(fast < nums.length){
if(nums[slow] != nums[fast]){
// 维护 nums[0..slow] 无重复
nums[++slow] = nums[fast];
}
fast++;
}
return slow+1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 83. 删除排序链表中的重复元素 (opens new window)
☀️☀️☀️☀️☀️☀️题解一：快慢指针
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return head;
ListNode slow = head,fast = head;
while(fast != null){
if(slow.val != fast.val){
slow.next = fast;
slow = slow.next;
}
fast=fast.next;
}
slow.next = null;
return head;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
☀️☀️☀️☀️☀️☀️题解二：dummy结点
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return head;
ListNode dummy = new ListNode(-101,head);
ListNode cur = head,pre = dummy;
while(cur != null){
if(cur.val != pre.val){
pre = pre.next;
}else{
pre.next = cur.next;
}
cur = cur.next;
}
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 27. 移除元素 (opens new window)
☀️☀️☀️☀️☀️☀️题解一：快慢指针
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];
// 维护 nums[0..slow-1] 结果集
}
fast++;
}
return slow;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 283. 移动零 (opens new window)
☀️☀️☀️☀️☀️☀️题解一：快慢指针
class Solution {
public void moveZeroes(int[] nums) {
int left = 0,right=0;
while(right < nums.length){
if(nums[right] != 0){
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
//nums[right] = 0;此处不能直接赋值为0，用例[1]跑不过，使用数据交换的方式
left++;
}
right++;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 二、左右指针
# 167. 两数之和 II - 输入有序数组 (opens new window)
☀️☀️☀️☀️☀️☀️题解一：
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){
return new int[]{left+1,right+1};
}else if(sum < target){
left++;
}else{
right--;
}
}
return new int[]{-1,-1};
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 344. 反转字符串 (opens new window)
☀️☀️☀️☀️☀️☀️题解一：
class Solution {
public void reverseString(char[] s) {
int left =0,right = s.length-1;
while(left < right){
char tmp = s[right];
s[right] = s[left];
s[left] = tmp;
left++;
right--;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 5. 最长回文子串 (opens new window)
☀️☀️☀️☀️☀️☀️题解一：中心扩展法
class Solution {
public String longestPalindrome(String s) {
String res = "";
//中心扩展
for(int i=0;i<s.length();i++){
String s1 = maxPlaindrome(s,i,i);
String s2 = maxPlaindrome(s,i,i+1);
res = s1.length()>res.length()?s1:res;
res = s2.length()>res.length()?s2:res;
}
return res;
}
public String maxPlaindrome(String s,int left,int right){
while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
return s.substring(left+1,right);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21