传统双指针

1 三数之和

15. 三数之和 - 力扣（LeetCode）

public List<List<Integer>> threeSum(int[] nums) {//对数组nums排序Arrays.sort(nums);//lists保存结果List<List<Integer>> lists = new ArrayList<>();int n = nums.length;for (int i = 0;i < n; i ++){int cur = nums[i];//如果cur大于0，则直接退出循环 if (cur > 0) break;//如果cur与之前一个元素相同，则跳过if (i > 0 && cur == nums[i - 1]) continue;//转成在[i+1,n-1]中求两数之和为target的问题int target = -nums[i];//定义左右指针int left = i + 1, right = n - 1;while (left < right){int lNum = nums[left];int rNum = nums[right];if (lNum + rNum == target){List<Integer> list = new ArrayList<>();list.add(cur);list.add(lNum);list.add(rNum);lists.add(list);//接着左指针右移 右指针左移 同时要跳过相同的数while(left + 1 < right && nums[left + 1] == lNum) left ++;while(left < right - 1 && nums[right - 1] == rNum) right --;left ++;right --;}else if (lNum + rNum > target){right --;}else{left ++;}}}return lists;
}

2 最长回文字符串

5. 最长回文子串 - 力扣（LeetCode）

思路**:两重for**循环 拿到所有可能长度的子串 根据下标判断子串是否回文串 若是判断是否需要更新 最长回文子串的[begin,end)

暴力解，用到了双指针

public String longestPalindrome(String s) {int n = s.length();char[] chars = s.toCharArray();//记录最长回文子串的长度int max = 0;//记录最长回文子串的起始下标int begin = 0;int end = 0;//i遍历所有起始位置   [i,j]for(int i = 0; i < n; i ++) {//j遍历所有结束位置for (int j = i; j < n; j ++){//若s下标[i,j]是回文串 if (isHW(chars,i,j)){//判断是否需要更新if (j - i + 1 > max){max = j - i + 1;begin = i;end = j + 1;}}}}return s.substring(begin, end);
}public boolean isHW(char[] chars,int left,int right){while(left <= right){if (chars[left] != chars[right]) return false;left ++;right --;}return true;
}

3 判断回文串

125. 验证回文串 - 力扣（LeetCode）

public boolean isPalindrome(String s) {//将所有大写字母转为小写字母s = s.toLowerCase();//将所有非小写字母 数字字符替换成空字符（移除所有非小写字母 数字字符）s = s.replaceAll("[^0-9a-z]","");int n = s.length();int left = 0, right = n - 1;while(left < right){char lc = s.charAt(left);char rc = s.charAt(right);if (lc != rc) return false;left ++;right --;}return true; }

4 回文子串

本人二面手撕代码原题，最优解要用到动态规划思想，我没有想出来，本人最后写出暴力解如下，暴力解思路就是拿到所有子串，判断子串是否是回文串，是数量就+1

647. 回文子串 - 力扣（LeetCode）

    public int getSumHw(String s){int n = s.length();char[] chars = s.toCharArray();int cnt = 0; //记录回文子串的数量for(int start = 0; start < n; start ++){for (int end = start + 1; end <= n; end++) {//判断s中[start,end) 是否是回文串if (isHW(chars, start, end)){cnt ++;}}}return cnt;}//判断chars数组中[start,end-1]下标组成的字符串是否是回文串private boolean isHW(char[] chars, int start, int end) { int left = start, right = end - 1;while (left < right){if (chars[left] != chars[right]) {return false;}left ++;right --;}return true;}