【数据结构】【数组与字符串】双指针的应用总结

清疚 2023-03-06 03:20 48阅读 0赞

> 导语：在刷完leetcode的数组与字符串的卡之后，发现数组和字符串的一些使用双指针算法有规则和套路；在leetcode上有对双指针使用的一些介绍，但是比较简单和只有两种；但是我刷的时候发现有三种，本文就说说自己总结的三种，以及在那些场景下想到使用该方法去解题。

##### 双指针技巧一：一个从开始，一个从结尾，两指针相遇 #####

*  直接上这种模式代码的模板；（go语言版本）

start :=0
    end := len(arr)-1
    for end > start {
        
    	// 相关的操作
    	start++
    	end--
    }

*  适用场景：

> 从目前遇到的题目来看，总结了两种场景下，需要考虑；其他场景后面遇到再补充
> 
>  *  用于一些数组的操作，对字符串进行翻转的交换，而不占用额外的空间；（注意给出的start和end并不是数组的0和len-1时候的操作）
>  *  数组是顺序的，而求某一个和值；注意：这里数组的要是顺序的，如果不是顺序的需要再考虑考虑
>  *  在一些特定场景下使用，是否需要先将数组进行排序呢

*  leetcode题目的分析

> 题目：翻转字符串  
> 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char\[\] 的形式给出。  
> 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。  
> 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。  
> 示例 1：  
> 输入：\[“h”,“e”,“l”,“l”,“o”\]  
> 输出：\[“o”,“l”,“l”,“e”,“h”\]  
> 分析： **典型的首尾指针相遇，直接用模板的代码，在操作出进行交换就可以**

> 两数之和 II - 输入有序数组  
> 给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。  
> 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。  
> 说明:  
> 返回的下标值（index1 和 index2）不是从零开始的。  
> 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。  
> 示例:  
> 输入: numbers = \[2, 7, 11, 15\], target = 9  
> 输出: \[1,2\]  
> 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

直接上代码

// 是模板的一种变种；增加了一种何时需要判断首指针和尾指针进行前进
    func twoSum(numbers []int, target int) []int {
        
    	start:=0
    	end := len(numbers)-1
    	result := []int{
        }
    	for end>start{
        
    		if numbers[start]+numbers[end]==target{
        
    			result = append(result,start+1)
    			result = append(result,end+1)
    			return result 
    		}else if (numbers[start]+numbers[end]>target{
        
    			end --
    		}else{
        
    			start ++
    		}
    	}
    	return result
    }

##### 双指针技巧二：快慢指针，两指针的运动方向相同 #####

*  适用场景

> 最终要的是 两个指针的移动策略  
> 你有时可能需要在使用双指针技巧之前对数组进行排序，也可能需要运用贪心法则来决定你的运动策略。  
> 一般情况是 不增加额外的空间，在数组中进行移动。满足的条件一般是字符串中一个特殊（相对于其他字符特殊）的**一个字符把字符串进行相隔可分成多段**（空格、1等）  
> 另外一种情况就是区间**特殊字符相隔**的区间最大值或最小值（这里面就要对比一下滑动窗口）

*  模板

index :=0
    for start:=0;start<len(arr);start++{
        
    	if arr[start]!=条件{
        
    		end  :=start
    		for end< len(arr) && arr[end]!=条件{
        
    			//arr[index] = arr[end] // 这里一般是向前补齐的操作
    			//index++  // 如果涉及到移动一般需要向前进行补齐
    			end++
    		}
    		// 这里一般做达到条件的一些操作
    		//reverse(s.begin() + idx - (end - start), s.begin() + idx);
    		start = end
    	}
    }

*  leetcode题目的分析

> leetcode485【简单】 最大连续1的个数  
> 给定一个二进制数组， 计算其中最大连续1的个数。  
> 示例 1:  
> 输入: \[1,1,0,1,1,1\]  
> 输出: 3  
> 解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.  
> 注意：  
> 输入的数组只包含 0 和1

> leetcode27 【简单】 移除元素

> leetcode 151 【中等】 翻转字符串里的单词  
> 给定一个字符串，逐个翻转字符串中的每个单词。  
> 示例 1：  
> 输入: “the sky is blue”  
> 输出: “blue is sky the”  
> 示例 2：  
> 输入: " hello world! "  
> 输出: “world! hello”  
> 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。  
> 示例 3：  
> 输入: “a good example”  
> 输出: “example good a”  
> 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。