双指针 --面试经典150题

验证回文串(easy)

做题过程

就是非常简单的双指针应用。

算法概述

原题

本题要求为判断一个字符串是否为回文（需跳过特殊字符进行匹配）。 双指针 。

• 时间复杂度为O(n)
• 空间复杂度为O(1)

JAVA

class Solution {
    public boolean isPalindrome(String s) {
        char[] cs = s.toCharArray(); 
        int m = 0, n = s.length() - 1;
        
        while (m < n) {
            // 跳过非字母或数字字符
            while (m < n && !Character.isLetterOrDigit(cs[m])) m++;
            while (m < n && !Character.isLetterOrDigit(cs[n])) n--;
            
            // 判断字符是否相等
            if (Character.toLowerCase(cs[m]) != Character.toLowerCase(cs[n])) {
                return false;
            }
            
            m++;
            n--;
        }
        return true;
    }
}

总结

要学会熟练使用这些转换字符的方法。

判断子序列(easy)

做题过程

简单双指针，但因为审题不仔细没有一次过。

算法概述

原题

本题要求为判断一字符串是否为另一字符串的子序列（相对位置不变，字符之间可以由其他字符）。 双指针 。

• 时间复杂度为O(n)
• 空间复杂度为O(1)

总结

仔细审题。

两数之和 II(medium)

做题过程

给出了加剪枝的解法，但实际上完全还是可以用哈希表的，除此之外，双指针还节省空间，但都因为思维固化，没有想到。

算法概述

原题

本题要求与两数之和大致相同，不同的是给的数组是递增的，同时需要返回索引。

• 时间复杂度为O(n)
• 空间复杂度为O(1)

JAVA

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

    }
}

总结

不要小瞧递增递减这种规律，不止在 双指针 类型的题目中，在很多类型的题目中，这样的趋势都是核心思路的核心部分。