Leetbook——数组和字符串（4）——头尾指针
四、双指针技巧（1）
头尾指针
1. 反转字符串
题目描述：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
解题方法：【头尾指针】
解题思路：
- 头指针i，尾指针j；
- 交换元素，并同时向中间移动
- 直到达到中间位置为止
复杂度分析：
时间复杂度：O(n)，n为输入字符串的长度，执行了n/2次交换
空间复杂度：O(1)，临时变量
代码：
public void reverseString(char[] s) {
int i = 0;
int j = s.length -1;
while(i <= s.length/2 && j >= s.length/2){
char temp = '0';
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
2. 数组拆分
题目描述：
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
解题方法：
解题思路：
- 升序排列
- 遍历：两两分组，找最小值（根据 i % 2 ！= 0进行判断）
- 最小值相加
复杂度分析：
时间复杂度：O(nlogn)，n为数组长度，为排序的时间复杂度【sort使用的是DualPivotQuicksort方法】
空间复杂度：O(logn) ,排序所需要的栈空间
代码：
public int arrayPairSum(int[] nums) {
//判断数组是否为空
if(nums.length == 0 || nums == null){
return 0;
}
Arrays.sort(nums);//排序
int sum = 0;
int min = 0;
for(int i = 0; i < nums.length ; i++){
if(i % 2 != 0){
//两两分组
min= Math.min(nums[i-1],nums[i]);//找最小值
sum += min;//相加
}
}
return sum;
}
3. 两数之和-输入有序数组
题目描述：
给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
解题方法一：暴力解法
解题思路：
- 双重循环
- 下标加1
复杂度分析：
时间复杂度：O(n^2)，n为数组长度，(双重循环)
空间复杂度：O(1)
代码：
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];//用于存放结果
//数组为空
if(numbers.length == 0 || numbers == null){
return new int[0];
}
//数组不为空
for(int i = 0; i < numbers.length; i++){
for(int j = i + 1; j <numbers.length; j++){
if(numbers[i] + numbers[j] == target ){
result = new int[]{
i+1,j+1};
}
}
}
return result;
}
}
解题方法二：二分查找
解题思路：
- 固定第一个数，寻找第二个数 = 目标值 - 第一个数
- 通过二分查找找第二个数（只在第一个数的右侧查找【避免下标重复】）
复杂度分析：
时间复杂度：O(nlogn)，n为数组长度，第一个数的确定,O(n)；二分查找第二个数O(logn)
空间复杂度：O(1)
代码：
class Solution {
public int[] twoSum(int[] numbers, int target) {
//数组为空
if(numbers.length == 0 || numbers == null){
return new int[0];
}
//数组不为空
for(int i = 0; i < numbers.length; i++){
//固定第一个数
int left = i+1, right = numbers.length - 1;
//二分查找
while(left <= right){
int mid = left + (right - left)/2;
if(target - numbers[i] == numbers[mid]){
return new int[]{
i+1, mid+1};
}else if(target - numbers[i] < numbers[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
}
}
return new int[0];
}
}
解题方法三：双指针
解题思路：
- 双指针（头尾往中间）
- 元素和 = 目标值，返回
元素和 < 目标值，头指针++；
元素和 > 目标值，尾指针–；
复杂度分析：
时间复杂度：O(n)，n为数组长度，两个指针移动的总次数为n次
空间复杂度：O(1)
代码：
public int[] twoSum(int[] numbers, int target) {
//数组为空
if(numbers.length == 0 || numbers == null){
return new int[0];
}
//数组不为空
int left = 0, right = numbers.length-1;//双指针
while(left < right){
if(numbers[left] + numbers[right] == target){
return new int[]{
left+1, right+1};
}else if(numbers[left] + numbers[right] < target){
left++;
}else{
right--;
}
}
return new int[0];
}
