双指针

双指针

Jason Lv3
  2023-09-10 08:38:05 2023-09-10 08:38:05 Created   2023-09-13 20:31:03 2023-09-13 20:31:03 Updated      999 Words  5 Mins  

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
On this page
双指针
  1. 167. 两数之和 II - 输入有序数组
  2. 1. 两数之和
  3. 633. 平方数之和
  4. 680. 验证回文串
  5. 88. 合并两个有序数组
  6. 142. 环形链表 II
  7. 1679. K 和数对的最大数目
  8. 392. 判断子序列
  9. 11. 盛最多水的容器
  11. 27. 移除元素