LeetCode 专题 ：双指针
LeetCode 第 167 题：两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
- 返回的下标值（index1 和 index2）不是从零开始的。
- 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
分析：看到有序，第 1 想到“二分查找”，但是我们这题，用“指针对撞”更合适。当然用哈希表也是可以的，不过哈希表的方法没有用到数组的有序性。
Python 代码：
class Solution:
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
# 有序数组，index1 必须小于 index2，用指针对撞是最合适的
size = len(numbers)
if size < 2:
return []
l = 0
r = size - 1
while l < r:
if numbers[l] + numbers[r] == target:
return [l + 1, r + 1]
elif numbers[l] + numbers[r] < target:
l += 1
else:
r -= 1
return []
Java 代码：
class Solution {
public int[] twoSum(int[] numbers, int target) {
int len = numbers.length;
int l = 0;
int r = len - 1;
while (l < r) {
int sum = numbers[l] + numbers[r];
if (sum > target) {
r--;
} else if (sum < target) {
l++;
} else {
int[] res = new int[2];
res[0] = l + 1;
res[1] = r + 1;
return res;
}
}
throw new IllegalArgumentException("输入数据有误");
}
}
Leetcode 第 125 题：验证回文串
传送门：英文网址：125. Valid Palindrome ，中文网址：125. 验证回文串 。
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama" 输出: true示例 2:
输入: "race a car" 输出: false
Python 代码：注意一写编码的细节
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
left = 0
right = len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
continue
if not s[right].isalnum():
right -= 1
continue
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
Leetcode 第 344 题：反转字符串
传送门：英文网址：344. Reverse String ，中文网址：344. 反转字符串 。
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
char[]的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]示例 2：
输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
Python 代码：
class Solution(object):
def reverseString(self, s):
"""
:type s: str
:rtype: str
"""
if len(s) < 2:
return s
left = 0
right = len(s) - 1
l = list(s)
# 重合在一个就没有交换的必要了，因此是 left < right
while left < right:
l[left], l[right] = l[right], l[left]
left += 1
right -= 1
return ''.join(l)
Leetcode 第 345 题：反转字符串中的元音字母
传送门：英文网址：345. Reverse Vowels of a String ，中文网址：345. 反转字符串中的元音字母 。
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1:
输入: "hello" 输出: "holle"示例 2:
输入: "leetcode" 输出: "leotcede"说明:
元音字母不包含字母"y"。
Python 代码：
class Solution(object):
def reverseVowels(self, s):
"""
:type s: str
:rtype: str
"""
vowels = set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])
s = list(s)
left = 0
right = len(s) - 1
while left < right:
if s[left] not in vowels:
left += 1
elif s[right] not in vowels:
right -= 1
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ''.join(s)
Leetcode 第 11 题：盛最多水的容器
传送门：英文网址：11. Container With Most Water ，中文网址：11. 盛最多水的容器 。
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
image
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7] 输出: 49
思路：贪心算法，总是贪心先固定容器的宽度。根据木桶原理（盛水的高度由最短的那块木板决定），高的那块木板往里面走，只可能让盛水越来越少，但是短板往里面走，却有可能让盛水越来越多。
Java 代码：
public class Solution {
// 指针对撞、贪心思想
// 参考解答：https://www.cnblogs.com/zichi/p/5745992.html
public int maxArea(int[] height) {
int len = height.length;
if (len < 2) {
// 0 或者 1 的时候，不能形成区间，所以不能形成容器
return 0;
}
int l = 0;
int r = len - 1;
int res = 0;
while (l < r) {
// 这里其实就是木桶原理，取决于最短的那根木板
// [1,2,3] 3 和 1 之间的长度就是 (3-1=)2
int area = (r - l) * Math.min(height[l], height[r]);
res = Math.max(res, area);
if (height[l] < height[r]) {
l++;
} else {
// height[l] >= height[r]
r--;
}
}
return res;
}
// 暴力解法，时间复杂度太高，我们应该使用指针对撞的方法
public int maxArea1(int[] height) {
int len = height.length;
if (len < 2) {
return 0;
}
int res = 0;
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
res = Integer.max(res, Integer.min(height[i], height[j]) * (j - i));
}
}
return res;
}
}
Python 代码：
class Solution:
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
l = 0
r = len(height) - 1
res = 0
while l < r:
min_h = min(height[l], height[r])
res = max(res, (r - l) * min_h)
if min_h == height[l]:
l += 1
else:
r -= 1
return res
if __name__ == '__main__':
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
solution = Solution()
result = solution.maxArea(height)
print(result)
参考资料：https://leetcode-cn.com/problems/container-with-most-water/solution/。
（本节完）
