双指针

双指针

Jason Lv3

167. 两数之和 II - 输入有序数组

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int[] twoSum(int[] numbers, int target) {
int i=0;
int j=numbers.length-1;
while(i<j){
if(target>numbers[i]+numbers[j]) i++;
else if(target<numbers[i]+numbers[j]) j--;
else return new int[]{i+1,j+1};
}
return new int[0];
}
}

以上是一有序数组 若为无序数组 那么双指针无效 请看下题

1. 两数之和

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for(int i = 0; i<nums.length; i++){
if(hashtable.containsKey(target-nums[i])){
return new int[]{hashtable.get(target-nums[i]),i};
}
hashtable.put(nums[i],i);
}
return new int[0];
}
}

633. 平方数之和

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public boolean judgeSquareSum(int c) {
long i=0;
long j=(long)Math.sqrt(c);
while(i<=j){
if(i*i+j*j==c) return true;
if(i*i+j*j<c) i++;
else j--;
}
return false;
}
}

注意int会溢出

680. 验证回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
int del = 0;
public boolean validPalindrome(String s) {
int left=0,right=s.length()-1;
while(left<right){
if(s.charAt(left)==s.charAt(right)) {
left++;
right--;
}
else{
if(del==0){
del++;
return validPalindrome(s.substring(left,right)) || validPalindrome(s.substring(left+1,right+1));
}
return false;
}
}
return true;
}
}

substring(left,right) 左闭右开
String.charAt(i) 返回第i个字符
String.length() 返回字符串长度

88. 合并两个有序数组

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 merge(int[] nums1, int m, int[] nums2, int n) {
int p1=0,p2=0,p3=0;
int[] nums3 = new int[m+n];
while(p1<m&&p2<n){
if(nums1[p1]<=nums2[p2]) nums3[p3++] = nums1[p1++];
else nums3[p3++] = nums2[p2++];
}
if(p1<m){
while(p1<m){
nums3[p3++] = nums1[p1++];
}
}
if(p2<n){
while(p2<n){
nums3[p3++] = nums2[p2++];
}
}
for(int i=0;i<m+n;i++){
nums1[i] = nums3[i];
}
}
}

142. 环形链表 II

快慢指针 相遇时 相差的距离为环的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast,slow;
fast = slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast) break;
}
if(fast == null || fast.next == null) return null;
slow = head;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}

images

1679. K 和数对的最大数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int maxOperations(int[] nums, int k) {
Arrays.sort(nums);
int end = nums.length-1;
int start = 0;
int count = 0;
while(start<end){
int sum = nums[start]+nums[end];
if(sum>k) end--;
else if (sum<k) start++;
else {
end--;
start++;
count++;
}
}
return count;
}
}

392. 判断子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean isSubsequence(String s, String t) {
if(s.equals("")) return true;
int len1 = s.length();
int len2 = t.length();
int count=0;
int i=0,j=0;
while(i<len1&&j<len2)
if(s.charAt(i)==t.charAt(j)){
i++;
j++;
count++;
if(count==len1) return true;
}else{
j++;
}
return false;

}
}

11. 盛最多水的容器

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 int maxArea(int[] height) {
int maxm = 0;
int start = 0;
int end = height.length-1;
int chang = height.length-1;
while(start < end){
int kuan = Math.min(height[start],height[end]);
if(maxm<chang*kuan){
maxm = chang*kuan;
}
if(height[start]<height[end]) {
start++;
chang--;
}else{
end--;
chang--;
}
}
return maxm;

}
}

⭐ left左边都是非零的 right持续向前移动 遇见非0就swap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public void moveZeroes(int[] nums) {
int left = 0;
int right =0;
while(right<nums.length){
if(nums[right]!=0){
int temp = nums[left];
nums[left] = nums[right];
nums[right]=temp;
left++;
}
right++;
}
}
}

27. 移除元素

⭐ 同上题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//方法一 覆盖
class Solution {
public int removeElement(int[] nums, int val) {
int left =0 ,right =0;
int len = nums.length;
int count=0;
while(right<len){
if(nums[right]!=val){
nums[left]=nums[right];
left++;
count++;
}
right++;
}
return count;
}
}

//方法二 同上题
// 输入:nums = [0,1,2,2,3,0,4,2], val = 2
//如果不等于val 两个指针一起走
//如果等于val 右指针走 左指针留下指向val 当右指针指向不是val时 交换
//最终结果就是 左指针的左都是满足条件的 左指针的右边都是不满足条件的
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
int right =0;
int count=0;
while(right<nums.length){
if(nums[right]!=val){
int temp = nums[left];
nums[left] = nums[right];
nums[right]=temp;
left++;
count++;
}
right++;
}
return count;
}
}
  • Title: 双指针
  • Author: Jason
  • Created at : 2023-09-10 08:38:05
  • Updated at : 2023-09-13 20:31:03
  • Link: https://xxxijason1201.github.io/2023/09/10/LeetCode/双指针/
  • License: This work is licensed under CC BY-NC-SA 4.0.
 Comments