LeetCode-双指针

1.有序数组的Two Sum

167. Two Sum II - Input array is sorted (Easy)
     LeetCode

思路：
1、双重循环
时间复杂度：O(N^2)

public int[] twoSum(int[] numbers, int target) {
        int len = numbers.length;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(numbers[i]+numbers[j] == target){
                    return new int[]{i+1,j+1};
                }
            }
        }
        return new int[]{};
    }

2、双指针
时间复杂度：O(N)

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

2.两数平方和

633. Sum of Square Numbers (Medium)
     LeetCode

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

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

345.reverse-vowels-of-a-string
LeetCode
思路：
1.利用首尾两个指针，当两个指针都遇到元音字母的时候交换两者；
如果有一个指向元音字母，另一个没有，则指向元音字母的指针要等一下另一个指针；
如何快速判断一个字符是否是元音字母？
将元音字母放到hashset中，判断是否包含就可以了

public static HashSet<Character> set = new HashSet(Arrays.asList(
        'a','e','i','o','u','A','E','I','O','U'
    ));

    public String reverseVowels(String s) {
        char[] arr = s.toCharArray();
        int pre = 0;
        int end = s.length() - 1;
        while(pre <= end){
            if(set.contains(arr[pre])&&set.contains(arr[end])){
                char temp = arr[pre];
                arr[pre] = arr[end];
                arr[end] = temp;
                pre++;
                end--;
            }else if(set.contains(arr[pre])&& !set.contains(arr[end])){
                end--;
            }else if(!set.contains(arr[pre])&& set.contains(arr[end])){
                pre++;
            }else{
                pre++;
                end--;
            }
        }
        return new String(arr);
    }

4.验证回文字符串 Ⅱ

680.valid-palindrome-ii
LeetCode
思路：
这里记录一个错误的解法，这个解法只考虑到了删除左侧的情况，而没有考虑到删除右侧的情况。

 public boolean validPalindrome(String s) {
        char[] arr = s.toCharArray();
        int start = 0,end = arr.length-1;
        boolean flag = false;
        while(start <= end){
            if(start == end && arr[start] == arr[end]){
                return true;
            }else if(arr[start] == arr[end]){
                start++;
                end--;
            }else{
                if(flag == false){
                    start++;
                    flag = true;
                    continue;
                }
                return false;
            }
        }
        return true;
    }

正确的解法是：
从两端开始遍历，如果一样则不进行操作，如果出现不一样，则进行左右减一个字符（逻辑或 ||）的判断

public boolean validPalindrome(String s) {
        for(int i=0,j=s.length()-1;i<j;i++,j--){
            if(s.charAt(i)!=s.charAt(j)){
                return isPalindrome(s,i,j-1) || isPalindrome(s,i+1,j);
            }
        }
        return true;
    }

    public boolean isPalindrome(String s,int i,int j){
        while(i < j){
            if(s.charAt(i++) != s.charAt(j--)){
                return false;
            }
        }
        return true;
    }

5.归并两个有序数组

88.merge-sorted-array
LeetCode

思路：
这题看似简单，实际还是有一丢丢难度的。
解题的关键在于res指针从后往前遍历，而不是从前往后。

//2020年11月24日
public void merge(int[] nums1, int m, int[] nums2, int n) {
        int top = m - 1;
        int bottom = n - 1;
        int res = (m + n) - 1;

        while ((top >= 0) || (bottom >= 0)) {
            if (top < 0) {
                nums1[res--] = nums2[bottom--];
            } else if (bottom < 0) {
                nums1[res--] = nums1[top--];
            } else if (nums1[top] > nums2[bottom]) {
                nums1[res--] = nums1[top--];
            } else {
                nums1[res--] = nums2[bottom--];
            }
        }
    }

6.判断链表是否存在环

141.linked-list-cycle
LeetCode

思路：
1.设置两个指针，一个步长为1，一个步长为2，他们如果相遇了，那么链表有环

//2020年11月24日
public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode one = head,two = head.next;
        while(one != null && two != null && two.next != null){
            if(one == two) return true;
            one = one.next;
            two = two.next.next;
        }
        return false;
    }

7.通过删除字母匹配到字典里最长单词

524.longest-word-in-dictionary-through-deleting
LeetCode
思路：
1.通过双指针判断target是否是s的子序列
使用compareTo()方法来比较两个字符串的字典序

//2020年11月28日
public String findLongestWord(String s, List<String> d) {
        String LongestWord = "";
        for(String target : d){
            int len1 = LongestWord.length();
            int len2 = target.length();
            if(len1 > len2 || (len1 == len2 && LongestWord.compareTo(target) < 0)){
                continue;
            }
            if(isSubstr(s,target)){
                LongestWord = target;
            }
        }
        return LongestWord;
    }

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