双指针之基础题目

文章目录

• 双指针之基础题目
• • 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.四数之和

双指针之基础题目 1.移除元素 1.1暴力解法

这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

很明显暴力解法的时间复杂度是O(n^2)，空间复杂度：O(1),这道题目暴力解法在leetcode上是可以过的

1.2双指针

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
}

2.反转字符串 2.1双指针法

func reverseString(s []byte)  {
    left:=0
    right:=len(s)-1
    for left<right{
        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 退出

在反转链表中，使用了双指针的方法。

那么反转字符串依然是使用双指针的方法，只不过对于字符串的反转，其实要比链表简单一些。

因为字符串也是一种数组，所以元素在内存中是连续分布，这就决定了反转链表和反转字符串方式上还是有所差异的。

对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。

以字符串hello为例，过程如下:

3.替换空格 3.1巧用公式

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.从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。

4.反转字符串里的单词 4.1巧用公式

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<len(b);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)。

不能使用辅助空间之后，那么只能在原字符串上下功夫了。

想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。

所以解题思路如下：
移除多余空格
将整个字符串反转
将每个单词反转
举个例子，源字符串为："the sky is blue "
移除多余空格 : “the sky is blue”
字符串反转：“eulb si yks eht”
单词反转：“blue is sky the”
这样我们就完成了翻转字符串里的单词
思路很明确了，我们说一说代码的实现细节，就拿移除多余空格来说:
那么使用双指针法来去移除空格，最后resize（重新设置）一下字符串的大小，就可以做到O(n)的时间复杂度。

如果对这个 *** 作比较生疏了，可以再看一下"移除元素"是如何移除元素的。

那么使用双指针来移除冗余空格代码如下： fastIndex走的快，slowIndex走的慢，最后slowIndex就标记着移除多余空格后新字符串的长度。

还做实现反转字符串的功能，支持反转字符串子区间，这个实现我们分别在"反转字符串"里已经讲过了。

5.翻转链表

单链表之基础题目

6.删除链表的倒数第N个节点

单链表之基础题目

7.链表相交

单链表之基础题目

8.环形链表II

单链表之基础题目

9.三数之和

哈希法之基础题目

10.四数之和

哈希法之基础题目