算法题型整理—双指针

整理双指针算法题型

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

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

两数之和

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        int[] result = new int[2];
        while (left < right) {
            int temp = numbers[left] + numbers[right];
            if (temp == target) {
                result[0] = left + 1;
                result[1] = right + 1;
                return result;
            } else if (temp > target) {
                right--;
            } else {
                left++;
            }
        }
        return null;
    }
}

两数平方和

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
两数平方和

class Solution {
    public boolean judgeSquareSum(int c) {
        double sqrtC = Math.sqrt(c);
        long num = (long) sqrtC;
        long left = 0;
        long right = num;
        while(left <= right) {
            long temp = left * left + right * right;
            if (c == temp) {
                return true;
            }
            if (c < temp) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }
}

反转字符串中的元音字符

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 ‘a’、‘e’、‘i’、‘o’、‘u’，且可能以大小写两种形式出现不止一次。

反转字符串中的元音字符

class Solution {
    
    public String reverseVowels(String s) {

        Set<Character> set = new HashSet();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        set.add('A');
        set.add('E');
        set.add('I');
        set.add('O');
        set.add('U'); 

        char[] charArray = s.toCharArray();
        int left = 0;
        int right = charArray.length - 1;
        char temp;
        while(left < right) {
            boolean containsLeft = set.contains(charArray[left]);
            boolean containsRight = set.contains(charArray[right]);
            if (containsLeft && containsRight) {
                temp = charArray[right];
                charArray[right] = charArray[left];
                charArray[left] = temp;
                left++;
                right--;
            }
            if (!containsLeft) {
                left++;
            }
            if(!containsRight) {
                right--;
            }
        }
        return new String(charArray);
    }
}

回文字符串

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

class Solution {
    public boolean validPalindrome(String s) {
        char[] charArray = s.toCharArray();
        int left = 0;
        int right = charArray.length - 1;
        boolean canSkip = true;

        while (left < right) {
            if (charArray[left] == charArray[right]) {
                left++;
                right--;
                continue;
            } else {
                if(canSkip) {
                    return innerValidPalindrome(charArray ,left + 1, right) || innerValidPalindrome(charArray, left, right - 1);
                } else {
                    return false;
                }
            }

        }
        return true;

    }

    public boolean innerValidPalindrome(char[] charArray, int left, int right) {
        if(left < 0 && right >= charArray.length) {
            return false;
        }
        while(left < right) {
            if (charArray[left] == charArray[right]) {
                left++;
                right--;
                continue;
            } else {
                return false;
            }
        }
        return true;
    }
}

归并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

归并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] resultArray = new int[n + m];
        int num1Start = 0;
        int num2Start = 0;
        int resultNum = 0;
        while (num1Start < m && num2Start < n) {
            if(nums1[num1Start] <= nums2[num2Start]) {
                resultArray[resultNum] = nums1[num1Start];
                resultNum++;
                num1Start++;
            } else {
                resultArray[resultNum] = nums2[num2Start];
                resultNum++;
                num2Start++;
            }
        }
            while(num1Start < m) {
                resultArray[resultNum] = nums1[num1Start];
                resultNum++;
                num1Start++;
            }


            while(num2Start < n) {
                resultArray[resultNum] = nums2[num2Start];
                resultNum++;
                num2Start++;
            }
        for(int i = 0; i < nums1.length; i++) {
            nums1[i] = resultArray[i];
        }
    }
}

判断链表是否存在环

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。
判断链表是否存在环

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slowNode = head;
        ListNode quickNode = head.next;
        while (slowNode != null && quickNode != null && quickNode.next != null) {
            if(slowNode == quickNode) {
                return true;
            }           
            slowNode = slowNode.next;
            quickNode = quickNode.next.next;
        }
        return false;
    }
}

最长子序列

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

最长子序列

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        if(s == null || s.length() == 0 || dictionary == null || dictionary.size() == 0) {
            return "";
        }
        dictionary.sort((o1, o2) -> {
            if (o1.length() != o2.length()) {
                return o2.length() - o1.length();
            } else {
                return o1.compareTo(o2);
            }
        });
        char[] targetArray = s.toCharArray();
        for(String word : dictionary) {
            if(compareWord(targetArray, word)) {
                return word;
            }
        }
        return "";

    }

    public boolean compareWord(char[] targetArray, String word) {
        char[] wordArray = word.toCharArray();
        int wordIndex = 0;
        int targetIndex = 0;
        while(wordIndex < wordArray.length && targetIndex < targetArray.length) {
            if(wordArray[wordIndex] == targetArray[targetIndex]) {
                wordIndex++;
                targetIndex++;
            } else {
                targetIndex++;
            }
        }
        if(wordIndex == wordArray.length) {
            return true;
        }
        return false;
    }
}