【力扣】面试经典150题——双指针

---

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

class Solution {public boolean isPalindrome(String s) {StringBuffer sgood = new StringBuffer();int length = s.length();for(int i = 0; i < length; i++){char ch = s.charAt(i);if(Character.isLetterOrDigit(ch)){  //判断是字母或数字sgood.append(Character.toLowerCase(ch));  //小写且拼接}}StringBuffer sgood_rev = new StringBuffer(sgood).reverse();  //复制且反转return sgood.toString().equals(sgood_rev.toString());  //判断}
}

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

class Solution {public boolean isSubsequence(String s, String t) {int n = s.length(), m = t.length();int i = 0, j = 0;while(i < n && j < m){if(s.charAt(i) == t.charAt(j)){i++;}j++;}return i == n;}
}

167. 两数之和 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) {for(int i = 0; i < numbers.length; ++i){int low = i + 1, high = numbers.length - 1;while(low <= high){int mid = (high - low) / 2 + low;if(numbers[mid] == target - numbers[i]){  //通过for循环，找出符合要求的return new int[]{i + 1, mid + 1};}else if(numbers[mid] > target - numbers[i]){  //中间值太大了high = mid - 1;}else{  //中间值太小了low = mid + 1;}}}return new int[]{-1, -1};}
}

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

class Solution {public int maxArea(int[] height) {int l = 0, r = height.length - 1;int ans = 0;while(l < r){int area = Math.min(height[l], height[r]) * (r - l);ans = Math.max(ans, area);if(height[l] <= height[r]){++l;}else{--r;}}return ans;}
}

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

class Solution {public List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<List<Integer>>();//枚举afor(int first = 0; first < n; ++first){//排除跟上一次枚举相同的数if(first > 0 && nums[first] == nums[first - 1]){continue;}//c 对应的指针初始指向数组最右端int third = n - 1;int target = -nums[first];//枚举bfor(int second = first + 1; second < n; ++second){//需要和上一次枚举的数不相同if(second > first + 1 && nums[second] == nums[second - 1]){continue;}//需要保证b的指针在c的指针的左侧while(second < third && nums[second] + nums[third] > target){--third;}//如果指针重合，随着b的增加//就不会满足 a+b+c=0 的情况if(second == third){break;}if(nums[second] + nums[third] == target){List<Integer> list = new ArrayList<Integer>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}
}

---