LeetCode 双指针算法

Question

1.有序数组的 Two Sum

167.给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

思路：使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        if(numbers == null) return null;
        int i = 0;
        int j = numbers.length - 1;
        while(i<j){
            int sum = numbers[i] + numbers[j];
            if(sum == target){
                return new int[]{i+1,j+1};
            }else if(sum < target){
                i++;
            }else{
                j--;
            }
        }
        return null;
        
    }
}

2.两数的平方和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

思路：可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。

本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。

class Solution {
    public boolean judgeSquareSum(int c) {
        if(c<0) return false;
        int i = 0;
        int j =(int)Math.sqrt(c);
        while(i<=j){
            int sum = i*i + j*j;
            if(sum == c){
                return true;
            }else if(sum < c){
                i++;
            }else{
                j--;
            }
        }
        return false;
    }
}

3.反转字符串中的元音字符

345.编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

输入: "hello"
输出: "holle"

思路：使用双指针，一个指针从头向尾遍历，一个指针从尾到头遍历，当两个指针都遍历到元音字符时，交换这两个元音字符。 为了快速判断一个字符是不是元音字符，我们将全部元音字符添加到集合 HashSet 中，从而以 O(1) 的时间复杂度进行该操作。

class Solution {
    private final static HashSet<Character> vowels = new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U')); 
    public String reverseVowels(String s) {
        if(s == null) return null;
        int i = 0;
        int j = s.length()-1;
        char[] result = new char[s.length()];
        while(i<=j){
            char ci = s.charAt(i);
            char cj = s.charAt(j);
            if(!vowels.contains(ci)){
                result[i] = ci;
                i++;
            }else if(!vowels.contains(cj)){
                result[j] = cj;
                j--;
            }else{
                result[i] = cj;
                result[j] = ci;
                i++;
                j--;
            }
        }
        return new String(result);
    }
}

4. 回文字符串

680.给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

思路：

本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。

在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。

在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。

class Solution {
    private boolean flag = true;
    public boolean validPalindrome(String s) {
        if(s == null) return false;
        int i = 0;
        int j = s.length() - 1;
        
        while(i<=j){
            char ci = s.charAt(i);
            char cj = s.charAt(j);
            if(ci != cj){
                if(!flag){
                    return false;
                }
                flag = false;
                return validPalindrome(s.substring(i,j)) || validPalindrome(s.substring(i+1,j+1));
            }
            i++;
            j--;
        }
        return true;
    }
}

5. 归并两个有序数组

88.给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

思路：需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        int i = m-1;
        int j = n-1;
        int k = m+n-1;
        while(i>=0||j>=0){
            if(i<0){
                nums1[k--] = nums2[j--];
            }else if(j<0){
                nums1[k--] = nums1[i--];
            }else if(nums1[i]>nums2[j]){
                nums1[k--] = nums1[i--];
            }else{
                nums1[k--] = nums2[j--];
            }
        }
    }
}

6.判断链表是否存在环

141.给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思路：快慢指针，使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode p1 = head;
        ListNode p2 = head.next;
        while(p1 != null && p2 !=null && p2.next != null){
            if(p1 == p2){
                return true;
            }
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return false;
     }
}

剑指 55.链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出 null。

思路：快慢指针。

1. 初始化：快指针 fast 指向头结点， 慢指针 slow 指向头结点
2. 让 fast 一次走两步， slow 一次走一步，第一次相遇在 C 处，停止
3. 然后让 fast 指向头结点，slow 原地不动，让后 fast，slow 每次走一步，当再次相遇，就是入口结点。

public class Solution {​
 public ListNode EntryNodeOfLoop(ListNode pHead)
 {
     if(pHead == null || pHead.next == null || pHead.next.next == null) return null;
     ListNode p1 = pHead.next, p2 = pHead.next.next;
     while(p1 != p2){
         if(p1.next == null || p2.next.next == null) return null;
         p1 = p1.next;
         p2 = p2.next.next;
     }
     p2 = pHead;
     while(p1 != p2){
         p1 = p1.next;
         p2 = p2.next;
     }
     return p2;
 }
}

7. 最长子序列

524.给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

输出: 
"apple"

思路：通过删除字符串 s 中的一个字符能得到字符串 t，可以认为 t 是 s 的子序列，我们可以使用双指针来判断一个字符串是否为另一个字符串的子序列。

class Solution {
    public String findLongestWord(String s, List<String> d) {
        String longestWord = "";
        for(String target : d){
            int l1 = longestWord.length();
            int l2 = target.length();
            if(l1 > l2 || (l1==l2 && longestWord.compareTo(target) <= 0)){
                continue;
            }
            if(isSub(s,target)){
                longestWord = target;
            }
        }
        return longestWord;
    }

    public boolean isSub(String s, String target){
        int i = 0;
        int j = 0;
        while(i < s.length() && j < target.length()){
            if(s.charAt(i) == target.charAt(j)){
                j ++;
            }
            i ++ ;
        }
        return j == target.length();
    }
}

8.三数之和

15.难度中等 2497 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路：排序，遍历数组，对每个数从两端再次寻找有无两数之和等于该数。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ls = new ArrayList<>();
 
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {  // 跳过可能重复的答案
 
                int l = i + 1, r = nums.length - 1, sum = 0 - nums[i];
                while (l < r) {
                    if (nums[l] + nums[r] == sum) {
                        ls.add(Arrays.asList(nums[i], nums[l], nums[r]));
                        while (l < r && nums[l] == nums[l + 1]) l++;
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        l++;
                        r--;
                    } else if (nums[l] + nums[r] < sum) {
                        while (l < r && nums[l] == nums[l + 1]) l++;   // 跳过重复值
                        l++;
                    } else {
                        while (l < r && nums[r] == nums[r - 1]) r--;
                        r--;
                    }
                }
            }
        }
        return ls;
    }
}