- 代码随想录之双指针系列基础题目
- 1.移除元素
- 1.1暴力解法
- 1.2双指针
- 2.反转字符串
- 2.1双指针法
- 3.替换空格
- 3.1巧用公式
- 3.2扩充数组
- 3.3双指针
- 4.反转字符串里的单词
- 4.1巧用公式
- 4.2双指针
- 5.翻转链表
- 6.删除链表的倒数第N个节点
- 7.链表相交
- 8.环形链表II
- 9.三数之和
- 10.四数之和
- 11.有序数组的平方
- 11.1暴力解法
- 11.2双指针
- 12.剑指Offer58 II--左旋转字符串
- 12.1双指针
- 13.反转字符串II
- 13.1双指针
- 14.剑指Offer57--和为s的两个数字
- 14.1双指针
- 15.删除有序数组中的重复项
- 15.1双指针
- 16.移动零
- 17.比较含退格的字符串
- 17.1重构字符串
- 17.2双指针
func removeElement(nums []int, val int) int {
len := len(nums)
for i := 0; i < len; i++ {
if nums[i] == val {// 发现需要移除的元素，就将数组集体向前移动一位
for j := i + 1; j < len; j++ {
nums[j-1] = nums[j]
}
i--// 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
len--// 此时数组的大小-1
}
}
return len
}
有的同学可能说了，多余的元素，删掉不就得了。
要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
1.2双指针这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
很明显暴力解法的时间复杂度是O(n^2)，空间复杂度：O(1),这道题目暴力解法在leetcode上是可以过的
func main() {
a := []int{3, 2, 2, 3}
fmt.Println(removeElement(a, 3)) //输出:2
fmt.Println(a) //输出:[2 2 2 3]
}
func removeElement(nums []int, val int) int {
left := 0
for _, v := range nums { // v 即 nums[right]
if v != val {
nums[left] = v
left++
}
}
return left
}
//时间复杂度:O(n).其中 n为序列的长度。我们只需要遍历该序列至多两次。
//空间复杂度：O(1).我们只需要常数的空间保存若干变量
注意：不管是暴力解法还是双指针，都并没有改变元素的相对位置！
双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
删除过程如下：
由于题目要求删除数组中等于val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。
可以使用双指针：右指针right 指向当前将要处理的元素，左指针left指向下一个将要赋值的位置。
如果右指针指向的元素不等于val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；
如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位。
整个过程保持不变的性质是：区间[0,left) 中的元素都不等于 val。当左右指针遍历完输入数组以后，left 的值就是输出数组的长度。
这样的算法在最坏情况下（输入数组中没有元素等于val），左右指针各遍历了数组一次,如下所示
func main() {
a := []int{3, 2, 2, 6}
fmt.Println(removeElement(a, 5)) //输出:4
fmt.Println(a) //输出:[2 2 2 6]
}
func removeElement(nums []int, val int) int {
length := len(nums)
res := 0
for i := 0; i < length; i++ {
if nums[i] != val {
nums[res] = nums[i]
res++
}
}
return res
}
相关题目推荐
26.删除排序数组中的重复项
283.移动零
844.比较含退格的字符串
977.有序数组的平方
双指针解法
func reverseString(s []byte) {
left:=0
right:=len(s)-1
for left
s[left],s[right]=s[right],s[left]
left++
right--
}
}
//时间复杂度：O(N)，其中 N 为字符数组的长度。一共执行了 N/2 次的交换。
//空间复杂度：O(1)。只使用了常数空间来存放若干变量
func reverseString(s string) string {
runes := []rune(s)
//定义一个最左边的索引与最右边的索引
for from, to := 0, len(runes)-1; from < to; from, to = from+1, to-1 {
runes[from], runes[to] = runes[to], runes[from]
}
return string(runes)
}
//测试
4个字符0 1 2 3
0 3 0<3 1 2
1<2 2 1
2>1 退出
//测试
5个字符0 1 2 3 4
0 4 0<4 1 3
1<3 2 2
2=2 退出
3.替换空格 3.1巧用公式在反转链表中，使用了双指针的方法。
那么反转字符串依然是使用双指针的方法，只不过对于字符串的反转，其实要比链表简单一些。
因为字符串也是一种数组，所以元素在内存中是连续分布，这就决定了反转链表和反转字符串方式上还是有所差异的。
对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。
以字符串hello为例，过程如下:
func replaceSpace(s string) string {
return strings.Replace(s," ","%20",-1)
}
3.2扩充数组
// 遍历添加
func replaceSpace(s string) string {
b := []byte(s)
result := make([]byte, 0)
for i := 0; i < len(b); i++ {
if b[i] == ' ' {
result = append(result, []byte("%20")...)//...不能省掉，append函数在添加切片的时候，必须得加...，否则编译不过
} else {
result = append(result, b[i])//
}
}
return string(result)
}
3.3双指针
// 原地修改
func replaceSpace(s string) string {
b := []byte(s)
length := len(b)
spaceCount := 0
// 计算空格数量
for _, v := range b {
if v == ' ' {
spaceCount++
}
}
// 扩展原有切片
resizeCount := spaceCount * 2
tmp := make([]byte, resizeCount)
b = append(b, tmp...)
i := length - 1//i指向新长度的末尾
j := len(b) - 1//j指向旧长度的末尾
for i >= 0 {
if b[i] != ' ' {
b[j] = b[i]
i--
j--
} else {//等于空格的时候
b[j] = '0'
b[j-1] = '2'
b[j-2] = '%'
i--
j = j - 3
}
}
return string(b)
}
//时间复杂度：O(n)
//空间复杂度：O(1)
如果想把这道题目做到极致，就不要只用额外的辅助空间了！
首先扩充数组到每个空格替换成"%20"之后的大小。
然后从后向前替换空格，也就是双指针法，过程如下：
i指向新长度的末尾，j指向旧长度的末尾。
有同学问了，为什么要从后向前填充，从前向后填充不行么？
从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
1.不用申请新数组。
2.从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。
func reverseWords(s string) string {
k := strings.Fields(s)
b := make([]string, 0)
for i := len(k) - 1; i >= 0; i-- {
b = append(b, k[i])
}
c := strings.Join(b, " ")
return c
}
//注意：本题不能用split函数
4.2双指针
func reverseWords(s string) string {
//1.使用双指针删除冗余的空格
slowIndex, fastIndex := 0, 0
b := []byte(s)
//删除头部冗余空格
for len(b) > 0 && fastIndex < len(b) && b[fastIndex] == ' ' {
fastIndex++
}
//删除单词间冗余空格
for ; fastIndex < len(b); fastIndex++ {
if fastIndex-1 > 0 && b[fastIndex-1] == b[fastIndex] && b[fastIndex] == ' ' {
continue
}
b[slowIndex] = b[fastIndex]
slowIndex++
}
//删除尾部冗余空格
if slowIndex-1 > 0 && b[slowIndex-1] == ' ' {
b = b[:slowIndex-1]
} else {
b = b[:slowIndex]
}
//2.反转整个字符串
reverse(b, 0, len(b)-1)
//3.反转单个单词 i单词开始位置，j单词结束位置
m:=0
for i:=0;i
if b[i]==' '{
reverse(b,m,i-1)
m=i+1
}
if i==len(b)-1{
reverse(b,m,len(b)-1)
}
}
return string(b)
}
func reverse( b []byte, left, right int) {
for left < right {
b[left], b[right] = b[right], b[left]
left++
right--
}
}
这道题目可以说是综合考察了字符串的多种操作。
一些同学会使用库函数，分隔单词，然后定义一个新的string字符串，最后再把单词倒序相加，那么这道题题目就是一道水题了，失去了它的意义。
所以这里我还是提高一下本题的难度：不要使用辅助空间，空间复杂度要求为O(1)。
不能使用辅助空间之后，那么只能在原字符串上下功夫了。
5.翻转链表想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。
所以解题思路如下：
移除多余空格
将整个字符串反转
将每个单词反转
举个例子，源字符串为："the sky is blue "
移除多余空格 : “the sky is blue”
字符串反转：“eulb si yks eht”
单词反转：“blue is sky the”
这样我们就完成了翻转字符串里的单词
思路很明确了，我们说一说代码的实现细节，就拿移除多余空格来说:
那么使用双指针法来去移除空格，最后resize（重新设置）一下字符串的大小，就可以做到O(n)的时间复杂度。
如果对这个操作比较生疏了，可以再看一下"移除元素"是如何移除元素的。
那么使用双指针来移除冗余空格代码如下： fastIndex走的快，slowIndex走的慢，最后slowIndex就标记着移除多余空格后新字符串的长度。
还做实现反转字符串的功能，支持反转字符串子区间，这个实现我们分别在"反转字符串"里已经讲过了。
单链表之基础题目
6.删除链表的倒数第N个节点单链表之基础题目
7.链表相交单链表之基础题目
8.环形链表II单链表之基础题目
9.三数之和哈希法之基础题目
10.四数之和哈希法之基础题目
11.有序数组的平方 11.1暴力解法func sortedSquares(nums []int) []int {
ans := make([]int, len(nums))
for i, v := range nums {
ans[i] = v * v
}
sort.Ints(ans)
return ans
}
11.2双指针最直观的想法，莫过于：每个数平方之后，排个序，美滋滋
这个时间复杂度是 O(n + nlogn)， 可以说是O(nlogn)的时间复杂度，但为了和下面双指针法算法时间复杂度有鲜明对比，我记为 O(n + nlog n)
func sortedSquares(nums []int) []int {
n := len(nums)
i, j, k := 0, n-1, n-1
ans := make([]int, n)
for i <= j {
lm, rm := nums[i]*nums[i], nums[j]*nums[j]
if lm > rm {
ans[k] = lm
i++
} else {
ans[k] = rm
j--
}
k--
}
return ans
}
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。
如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。
如动画所示：
此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。
这里还是说一下，大家不必太在意leetcode上执行用时，打败多少多少用户，这个就是一个玩具，非常不准确。
做题的时候自己能分析出来时间复杂度就可以了，至于leetcode上执行用时，大概看一下就行，只要达到最优的时间复杂度就可以了，
一样的代码多提交几次可能就击败百分之百了
977.有序数组的平方
12.剑指Offer58 II–左旋转字符串 12.1双指针func reverseLeftWords(s string, n int) string {
b := []byte(s)
// 1. 反转前n个字符
// 2. 反转第n到end字符
// 3. 反转整个字符
reverse(b, 0, n-1)
reverse(b, n, len(b)-1)
reverse(b, 0, len(b)-1)
return string(b)
}
// 切片是引用传递
func reverse(b []byte, left, right int){
for left < right{
b[left], b[right] = b[right],b[left]
left++
right--
}
}
为了让本题更有意义，提升一下本题难度：不能申请额外空间，只能在本串上操作。
不能使用额外空间的话，模拟在本串操作要实现左旋转字符串的功能还是有点困难的。
那么我们可以想一下上一题目"151翻转字符串里的单词 "中讲过，使用整体反转+局部反转就可以实现，反转单词顺序的目的。
这道题目也非常类似，依然可以通过局部反转+整体反转 达到左旋转的目的。
具体步骤为：
1.反转区间为前n的子串
2.反转区间为n到末尾的子串
3.反转整个字符串
最后就可以得到左旋n的目的，而不用定义新的字符串，完全在本串上操作。
例如 ：示例1中 输入：字符串abcdefg，n=2
最终得到左旋2个单元的字符串：cdefgab
思路明确之后，那么代码实现就很简单了
总结:
13.反转字符串II 13.1双指针func reverseStr(s string, k int) string {
ss := []byte(s)
length := len(s)
for i := 0; i < length; i += 2 * k {
if length-i>=k {
reverse(ss[i:i+k])//如果剩余字符大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
} else if length-i//对应着如果剩余字符少于 k 个，则将剩余字符全部反转。
reverse(ss[i:length])
}
}
return string(ss)
}
func reverse(b []byte) {
left := 0
right := len(b) - 1
for left < right {
b[left], b[right] = b[right], b[left]
left++
right--
}
}
14.剑指Offer57–和为s的两个数字
14.1双指针
func reverseLeftWords(s string, n int) string {
b := []byte(s)
// 1. 反转前n个字符
// 2. 反转第n到end字符
// 3. 反转整个字符
reverse(b, 0, n-1)
reverse(b, n, len(b)-1)
reverse(b, 0, len(b)-1)
return string(b)
}
// 切片是引用传递
func reverse(b []byte, left, right int){
for left < right{
b[left], b[right] = b[right],b[left]
left++
right--
}
}
15.删除有序数组中的重复项
15.1双指针
func removeDuplicates(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
slow := 1
for fast := 1; fast < n; fast++ {
if nums[fast] != nums[fast-1] {
nums[slow] = nums[fast]
slow++
}
}
return slow
}
//时间复杂度：O(n)，其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。
//空间复杂度：OO(1)。只需要使用常数的额外空间。
《Leecode之双指针系列题目》
17.比较含退格的字符串 17.1重构字符串func build(str string) string {
s := []byte{}
for i := range str {
if str[i] != '#' {
s = append(s, str[i])
} else if len(s) > 0 {
s = s[:len(s)-1]
}
}
return string(s)
}
func backspaceCompare(s, t string) bool {
return build(s) == build(t)
}
//时间复杂度：O(N+M)，其中 N 和 M 分别为字符串 S和 T的长度。我们需要遍历两字符串各一次。
//空间复杂度：O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度。主要为还原出的字符串的开销。
17.2双指针
func backspaceCompare(s, t string) bool {
skipS, skipT := 0, 0
i, j := len(s)-1, len(t)-1
for i >= 0 || j >= 0 {
for i >= 0 {
if s[i] == '#' {
skipS++
i--
} else if skipS > 0 {
skipS--
i--
} else {
break
}
}
for j >= 0 {
if t[j] == '#' {
skipT++
j--
} else if skipT > 0 {
skipT--
j--
} else {
break
}
}
if i >= 0 && j >= 0 {
if s[i] != t[j] {
return false
}
} else if i >= 0 || j >= 0 {
return false
}
i--
j--
}
return true
}
//时间复杂度：O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。
//空间复杂度：O(1)。对于每个字符串，我们只需要定义一个指针和一个计数器即可。
