1. 背景
双指针能够巧妙解决一些leetcode的算法问题,做个总结便利自己做出一些规则总结,便利举一反三
2. demo
2.1 392. 判别子序列
给定字符串s和t,判别s是否为t的子序列。
public class Leetcode392Bak {
public boolean isSubsequence(String s, String t) {
int length = t.length();
int j = 0;
for (int i = 0; i < length && j < s.length() ; i++) {
if (t.charAt(i) == s.charAt(j)){
j ++;
}
}
return j == s.length();
}
}
des: 一定要预防短的指针发生index out of range的状况
2.2 125.验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都相同。则能够认为该短语是一个回文串。
public boolean isPalindrome(String s) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isLetterOrDigit(c)){
sb.append(Character.toLowerCase(c));
}
}
return new StringBuffer(sb).reverse().toString().equals(sb.toString());
}
2.3 167.两数之和 II – 输入有序数组
两个指针渐渐的缩进
public int[] twoSum(int[] numbers, int target) {
int i = 0;
int j = numbers.length - 1;
while (i < j){
if (numbers[i] + numbers[j] < target ){
i ++;
} else if (numbers[i] + numbers[j] > target) {
j --;
} else {
return new int[]{i + 1, j + 1};
}
}
return new int[]{-1, -1};
}