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];    	
}