Double pointers are mainly used to traverse arrays, and two pointers point to different elements, so as to cooperate to complete tasks.

1. Two Sum of ordered array

Leetcode-167. Sum of two numbers II - input ordered array

Given an ordered array in ascending order, find two numbers so that the sum of them is equal to the target number.

The function should return these two subscript values, index1 and index2, where index1 must be less than index2.

Explain:

• The returned subscript values (index1 and index2) are not zero based.
• You can assume that each input only corresponds to a unique answer, and you can't reuse the same element.

Example:

Enter: numbers = [2, 7, 11, 15], target = 9
 Output: [1,2]
Explanation: the sum of 2 and 7 is equal to the target number 9. So index1 = 1, index2 = 2.

Solution:

• Java

Use two pointers, one for elements with smaller values and one for elements with larger values. The pointer to the smaller element traverses from the beginning to the end, and the pointer to the larger element traverses from the end to the end.

If two pointers point to the sum of the element sum == target, the required result is obtained;

• If sum > target, move the larger elements to make sum smaller;
• If sum < target, move the smaller elements to make sum larger.

The elements in the array are traversed at most once, with a time complexity of O(N). Only two additional variables are used, with a spatial complexity of O(1).

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

2. Sum of squares of two numbers

Leetcode-633. Sum of squares

Given a non negative integer c, you need to determine whether there are two integers a and b, so that a2 + b2 = c.

Example 1:

Input: 5
 Output: True
 Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
 Output: False

Solution:

• Java

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

3. Reverse the vowel character in the string

Leetcode-345. Inverting vowels in a string

Write a function that takes a string as input and reverses the vowels in the string.

Example 1:

Input: "hello"
Output: "hole"

Example 2:

Input: "leetcode"
Output: "leotcede"

Explain:
Vowels do not contain the letter "y".

Solution:

• Java

class Solution {
    public String reverseVowels(String s) {
        Set<Character> set = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        int l = 0, h = s.length()-1;
        char[] res = new char[s.length()];
        while (l <= h) {
            char left = s.charAt(l);
            char right = s.charAt(h);
            if (set.contains(left) && set.contains(right)) {
                res[l++] = right;
                res[h--] = left;
            }
            else if (set.contains(left)) {
                res[h--] = right;
            }
            else if(set.contains(right)) {
                res[l++] = left;
            }
            else {
                res[l++] = left;
                res[h--] = right;
            }
        }
        return new String(res);
    }
}

4. Palindrome string

Leetcode-680. Verify palindrome string II

Given a non empty string s, delete at most one character. Determine whether it can be a palindrome string.

Example 1:

Enter: "aba"
Output: True

Example 2:

Enter: "abca"
Output: True
 Explanation: you can delete the c character.

Be careful:

1. The string contains only lowercase letters from a-z. The maximum length of the string is 50000.

Solution:

• Java

class Solution {
    public boolean validPalindrome(String s) {
        for (int l=0, h=s.length()-1; l<h; l++, h--) {
            if (s.charAt(l) != s.charAt(h)) return isPalindrome(s, l+1, h) || isPalindrome(s, l, h-1);        
        }
        return true;
    }
    private boolean isPalindrome(String s, int l, int h) {
        while (l<h) {
            if (s.charAt(l++)!=s.charAt(h--)) return false;
        }
        return true;
    }
}

5. Merge two ordered arrays

Leetcode-88. Merge two ordered arrays

Given two ordered integer arrays nums1 and nums2, nums2 is merged into nums1, making num1 an ordered array.

Explain:

• The number of elements to initialize nums1 and nums2 is m and n, respectively.
• You can assume that nums1 has enough space (space size greater than or equal to m + n) to hold the elements in nums2.

Example:

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

Output: [1,2,2,3,5,6]

Solution:

• Java

Need reverse order

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int r1 = m-1, r2 = n-1, put = m+n-1;
        while (r1>=0 || r2>=0) {
            if (r1 < 0) nums1[put--] = nums2[r2--];
            else if (r2 < 0) break; // The rest of nums1 is in order
            else if (nums1[r1] > nums2[r2]) nums1[put--] = nums1[r1--];
            else nums1[put--] = nums2[r2--];
        }
    }
}

6. Judge whether there is a link in the list

Leetcode-141. Circular list

Given a link list, determine whether there are links in the link list.

In order to represent the links in a given linked list, we use the integer pos to represent the position where the end of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there are no rings in the list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
 Output: true
 Explanation: there is a link in the list with the tail connected to the second node.

Example 2:

Input: head = [1,2], pos = 0
 Output: true
 Explanation: there is a link in the list with the tail connected to the first node.

Example 3:

Input: head = [1], pos = -1
 Output: false
 Explanation: there are no links in the list.

Advance:

Can you use O(1) (that is, constant) memory to solve this problem?

Solution:

Using double pointers, a pointer moves one node at a time, and a pointer moves two nodes at a time. If there is a ring, the two pointers will meet.

• Java

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

7. Longest subsequence

Leetcode-524. Match the longest word in the dictionary by deleting letters

Given a string and a string dictionary, find the longest string in the dictionary. The string can be obtained by deleting some characters of the given string. If there is more than one answer, returns the longest string with the least dictionary order. If the answer does not exist, an empty string is returned.

Example 1:

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

//Output: 
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"

Explain:

1. All input strings contain only lowercase letters.
2. The size of the dictionary will not exceed 1000.
3. All input strings will not be longer than 1000.

Solution:

• Java

class Solution {
    public String findLongestWord(String s, List<String> d) {
        int l = 0, maxCount = 0;
        String res = "";
        for (String str: d) {
            int count = 0;
            if (isSubstring(s, str)) {
                count = str.length();
                if (count>maxCount) {
                    maxCount = count;
                    res = str;
                }
                if (count==maxCount) res = smallerString(res, str);
            }
        }
        return res;
    }
    private boolean isSubstring(String str1, String str2) {
        if (str1.length() < str2.length()) return false;
        int l1 = 0, l2 = 0;
        while (l1<str1.length() && l2<str2.length()) {
            if (str1.charAt(l1) == str2.charAt(l2)) {
                l2++;
            }
            l1++;
        }
        return l2==str2.length();
    }
    
    private String smallerString(String str1, String str2) {
        if (str1.length()<1) return str1;
        if (str1.charAt(0) == str2.charAt(0)) return str1.charAt(0) + smallerString(str1.substring(1), str2.substring(1));
        else if (str1.charAt(0) > str2.charAt(0)) return str2;
        else return str1;
    }
}

Or use compareTo (more convenient)

class Solution {
    public String findLongestWord(String s, List<String> d) {
        int l = 0, maxCount = 0;
        String res = "";
        for (String str: d) {
            int count = 0;
            if (isSubstring(s, str)) {
                count = str.length();
                if (count>maxCount) {
                    maxCount = count;
                    res = str;
                }
                if (count==maxCount && res.compareTo(str)>0) res = str;
            }
        }
        return res;
    }
    private boolean isSubstring(String str1, String str2) {
        if (str1.length() < str2.length()) return false;
        int l1 = 0, l2 = 0;
        while (l1<str1.length() && l2<str2.length()) {
            if (str1.charAt(l1) == str2.charAt(l2)) {
                l2++;
            }
            l1++;
        }
        return l2==str2.length();
    }