LeetCode Go · 双指针（1）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

15. 三数之和

中等1 种解法

标签：数组、双指针、排序

题目、示例与约束

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

 

 

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

 

提示：

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

方法一：排序 + 双指针 · Go 实现

思考

三重循环枚举后再用集合去重，时间复杂度为 $O(n^3)$。 $n\le 3000$，无法通过。固定一个数后，问题退化为两数之和，哈希表可以将时间降至 $O(n^2)$，但去重较繁琐，也需要额外空间。

题目并不要求三元组按原顺序返回。先将数组排序，重复元素会相邻，便于跳过；有序之后，两数之和可以用左右指针在线性时间内完成。若 $nums[i]>0$，其后均为正数，三数之和不可能为 $0$，可以直接结束。因此排序后枚举第一个数，在右侧用双指针夹逼即可。

我们注意到，题目不要求我们按照顺序返回三元组，因此我们不妨先对数组进行排序，这样就可以方便地跳过重复的元素。

接下来，我们枚举三元组的第一个元素 $nums[i]$，其中 $0\le i<n-2$。对于每个 $i$，我们可以通过维护两个指针 $j=i+1$ 和 $k=n-1$，从而找到满足 $nums[i]+nums[j]+nums[k]=0$ 的 $j$ 和 $k$。在枚举的过程中，我们需要跳过重复的元素，以避免出现重复的三元组。

具体判断逻辑如下：

如果 $i>0$ 并且 $nums[i]=nums[i-1]$，则说明当前枚举的元素与上一个元素相同，我们可以直接跳过，因为不会产生新的结果。

如果 $nums[i]>0$，则说明当前枚举的元素大于 $0$，则三数之和必然无法等于 $0$，结束枚举。

否则，我们令左指针 $j=i+1$，右指针 $k=n-1$，当 $j<k$ 时，执行循环，计算三数之和 $x=nums[i]+nums[j]+nums[k]$，并与 $0$ 比较：

• 如果 $x<0$，则说明 $nums[j]$ 太小，我们需要将 $j$ 右移一位。
• 如果 $x>0$，则说明 $nums[k]$ 太大，我们需要将 $k$ 左移一位。
• 否则，说明我们找到了一个合法的三元组，将其加入答案，并将 $j$ 右移一位，将 $k$ 左移一位，同时跳过所有重复的元素，继续寻找下一个合法的三元组。

枚举结束后，我们即可得到三元组的答案。

时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组的长度。

func threeSum(nums []int) (ans [][]int) {
	sort.Ints(nums)
	n := len(nums)
	for i := 0; i < n-2 && nums[i] <= 0; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		j, k := i+1, n-1
		for j < k {
			x := nums[i] + nums[j] + nums[k]
			if x < 0 {
				j++
			} else if x > 0 {
				k--
			} else {
				ans = append(ans, []int{nums[i], nums[j], nums[k]})
				j, k = j+1, k-1
				for j < k && nums[j] == nums[j-1] {
					j++
				}
				for j < k && nums[k] == nums[k+1] {
					k--
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

16. 最接近的三数之和

中等1 种解法

标签：数组、双指针、排序

题目、示例与约束

给定一个长度为 n 的整数数组 nums 和 一个整数 target。

请你从 nums 中选出三个在 不同下标位置 的整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在 恰好 一个解。

 

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。

示例 2：

输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

 

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

方法一：排序 + 双指针 · Go 实现

思考

若枚举所有三元组并记录与 $target$ 最接近的和，时间复杂度为 $O(n^3)$。 $n\le 1000$，无法通过。

固定一个数后，问题退化为在剩余数组中找两个数，使其和最接近给定值。我们并不需要全部三元组，只要最接近 $target$ 的那个和。将数组排序后：若当前和偏大，只能缩小右端；若偏小，只能增大左端；若恰好等于 $target$，已经是最优。

因此枚举第一个数，在右侧用双指针按与 $target$ 的大小夹逼，并维护最小偏差。题目保证答案唯一，不必处理重复。

我们将数组排序，然后遍历数组，对于每个元素 $nums[i]$，我们使用指针 $j$ 和 $k$ 分别指向 $i+1$ 和 $n-1$，计算三数之和，如果三数之和等于 $target$，则直接返回 $target$，否则根据与 $target$ 的差值更新答案。如果三数之和大于 $target$，则将 $k$ 向左移动一位，否则将 $j$ 向右移动一位。

时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。

func threeSumClosest(nums []int, target int) int {
	sort.Ints(nums)
	ans := 1 << 30
	n := len(nums)
	for i, v := range nums {
		j, k := i+1, n-1
		for j < k {
			t := v + nums[j] + nums[k]
			if t == target {
				return t
			}
			if abs(t-target) < abs(ans-target) {
				ans = t
			}
			if t > target {
				k--
			} else {
				j++
			}
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

18. 四数之和

中等1 种解法

标签：数组、双指针、排序

题目、示例与约束

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

 

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

 

提示：

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

方法一：排序 + 双指针 · Go 实现

思考

四重循环枚举后再用集合去重，时间复杂度为 $O(n^4)$。 $n\le 200$，难以通过。固定前两个数之后，问题退化为两数之和，哈希表可以将内层降至线性，但去重较繁琐，也需要额外空间。

题目要求四元组不重复，并不限定原顺序。先将数组排序，重复元素会相邻，枚举 $i$、 $j$ 时跳过相同值即可；有序之后，剩下的两数之和可以用左右指针在线性时间内完成。因此排序后两层枚举前两个数，在右侧用双指针夹逼，时间降至 $O(n^3)$。

我们注意到，题目中要求找到不重复的四元组，那么我们可以先对数组进行排序，这样就可以方便地跳过重复的元素。

接下来，我们枚举四元组的前两个元素 $nums[i]$ 和 $nums[j]$，其中 $i<j$，在枚举的过程中，我们跳过重复的 $nums[i]$ 和 $nums[j]$。然后，我们用两个指针 $k$ 和 $l$ 分别指向 $nums[i]$ 和 $nums[j]$ 后面的两端，令 $x=nums[i]+nums[j]+nums[k]+nums[l]$，我们将 $x$ 与 $target$ 比较，进行如下操作：

• 如果 $x<target$，则更新 $k=k+1$ 以得到更大的 $x$；
• 如果 $x>target$，则更新 $l=l-1$ 以得到更小的 $x$；
• 否则，说明找到了一个四元组 $(nums[i],nums[j],nums[k],nums[l])$，将其加入答案，然后我们更新指针 $k$ 和 $l$，并跳过所有重复的元素，防止答案中包含重复的四元组，继续寻找下一个四元组。

时间复杂度为 $O(n^3)$，空间复杂度为 $O(\log n)$，其中 $n$ 是数组的长度。

func fourSum(nums []int, target int) (ans [][]int) {
	n := len(nums)
	if n < 4 {
		return
	}
	sort.Ints(nums)
	for i := 0; i < n-3; i++ {
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < n-2; j++ {
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			k, l := j+1, n-1
			for k < l {
				x := nums[i] + nums[j] + nums[k] + nums[l]
				if x < target {
					k++
				} else if x > target {
					l--
				} else {
					ans = append(ans, []int{nums[i], nums[j], nums[k], nums[l]})
					k++
					l--
					for k < l && nums[k] == nums[k-1] {
						k++
					}
					for k < l && nums[l] == nums[l+1] {
						l--
					}
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

26. 删除有序数组中的重复项

简单1 种解法

标签：数组、双指针

题目、示例与约束

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。

nums 的前 k 个元素应包含 排序后 的唯一数字。下标 k - 1 之后的剩余元素可以忽略。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

 

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4,_,_,_,_,_]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

 

提示：

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• nums 已按 非递减 顺序排列。

方法一：一次遍历 · Go 实现

思考

数组已经按非递减排列，重复元素必然相邻。若另开哈希表记录已经出现过的值再写回数组，时间 $O(n)$。在 $n\le 3\times {10}^4$ 的数据范围下可以接受，但题目要求原地修改，额外的线性空间并不必要。

因此判断当前值是否该保留，只需看它是否等于已经写下的最后一个数，而不必全局查表。为此用 $k$ 同时充当写指针与去重后的长度：仅当尚未写下任何元素，或当前值与 $nums[k-1]$ 不同时，才覆盖到位置 $k$。一遍扫描，额外空间 $O(1)$。

我们用一个变量 $k$ 记录当前已经处理好的数组的长度，初始时 $k=0$，表示空数组。

然后我们从左到右遍历数组，对于遍历到的每个元素 $x$，如果 $k=0$ 或者 $x\ne nums[k-1]$，我们就将 $x$ 放到 $nums[k]$ 的位置，然后 $k$ 自增 $1$。否则， $x$ 与 $nums[k-1]$ 相同，我们直接跳过这个元素。继续遍历，直到遍历完整个数组。

这样，当遍历结束时， $nums$ 中前 $k$ 个元素就是我们要求的答案，且 $k$ 就是答案的长度。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组的长度。

补充：

原问题要求最多相同的数字最多出现 $1$ 次，我们可以扩展至相同的数字最多保留 $k$ 个。

• 由于相同的数字最多保留 $k$ 个，那么原数组的前 $k$ 个元素我们可以直接保留；
• 对于后面的数字，能够保留的前提是：当前数字 $x$ 与前面已保留的数字的倒数第 $k$ 个元素比较，不同则保留，相同则跳过。

相似题目：

• 80. 删除有序数组中的重复项 II

func removeDuplicates(nums []int) int {
	k := 0
	for _, x := range nums {
		if k == 0 || x != nums[k-1] {
			nums[k] = x
			k++
		}
	}
	return k
}

力扣原题 · Doocs 题解来源

27. 移除元素

简单1 种解法

标签：数组、双指针

题目、示例与约束

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

 

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

 

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

方法一：一次遍历 · Go 实现

思考

题目要求原地移除所有等于 $val$ 的元素。若另开数组拷贝剩余元素，时间 $O(n)$， $n\le 100$ 可以接受，但多一次分配并不必要。

若每次删除都把后面的元素整体前移，最坏时间 $O(n^2)$。评测只要求前 $k$ 个位置覆盖全部非 $val$ 元素，相对顺序可以改变。

因此不必真正「删除」，把需要保留的值依次覆盖到数组前部即可。用 $k$ 记录已写下的个数，遇 $x\ne val$ 则写入 $nums[k]$ 并将 $k$ 加一。一遍扫描，额外空间 $O(1)$。

我们用变量 $k$ 记录当前不等于 $val$ 的元素个数。

遍历数组 $nums$，如果当前元素 $x$ 不等于 $val$，则将 $x$ 赋值给 $nums[k]$，并将 $k$ 自增 $1$。

最后返回 $k$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $nums$ 的长度。

func removeElement(nums []int, val int) int {
	k := 0
	for _, x := range nums {
		if x != val {
			nums[k] = x
			k++
		}
	}
	return k
}

力扣原题 · Doocs 题解来源

28. 找出字符串中第一个匹配项的下标

简单3 种解法

标签：双指针、字符串、字符串匹配、KMP 算法、Boyer–Moore 算法、扩展 KMP

题目、示例与约束

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

 

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

 

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

方法一：遍历 · Go 实现

思考

若以 $haystack$ 的每个位置 $i$ 为起点，检查长度为 $m$ 的子串是否等于 $needle$，时间复杂度为 $O((n-m)m)$。在 $n,m\le {10}^4$ 的数据范围下可以接受。

我们只关心第一次出现的下标，因此一旦某起点匹配成功即可返回；失配则换下一个 $i$，不必收集全部出现位置。窗口之间不复用比较结果，直接比对即可，额外空间 $O(1)$。

以字符串 haystack 的每一个字符为起点与字符串 needle 进行比较，若发现能够匹配的索引，直接返回即可。

假设字符串 haystack 长度为 $n$，字符串 needle 长度为 $m$，则时间复杂度为 $O((n-m)\times m)$，空间复杂度 $O(1)$。

func strStr(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	for i := 0; i <= n-m; i++ {
		if haystack[i:i+m] == needle {
			return i
		}
	}
	return -1
}

方法二：Rabin-Karp 字符串匹配算法 · Go 实现

思考

方法一最坏每个起点都要比满 $m$ 个字符，接近 $O(nm)$。我们希望窗口滑动时复用上一次的比较信息。

固定长度的子串可以用滚动哈希：右端纳入一个字符、左端移出一个字符，哈希值即可 $O(1)$ 更新。当窗口哈希等于 $needle$ 的哈希时再核对原串，以避免冲突造成误报。

因此只需扫描一遍 $haystack$，期望时间 $O(n+m)$。

Rabin-Karp 算法本质上是利用滑动窗口配合哈希函数对固定长度的字符串哈希之后进行比较，可以将比较两个字符串是否相同的时间复杂度降为 $O(1)$。

假设字符串 haystack 长度为 $n$，字符串 needle 长度为 $m$，则时间复杂度为 $O(n+m)$，空间复杂度 $O(1)$。

func strStr(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	sha, target, left, right, mod := 0, 0, 0, 0, 1<<31-1
	multi := 1
	for i := 0; i < m; i++ {
		target = (target*256%mod + int(needle[i])) % mod
	}
	for i := 1; i < m; i++ {
		multi = multi * 256 % mod
	}

	for ; right < n; right++ {
		sha = (sha*256%mod + int(haystack[right])) % mod
		if right-left+1 < m {
			continue
		}
		// 此时 left~right 的长度已经为 needle 的长度 m 了，只需要比对 sha 值与 target 是否一致即可
		// 为避免 hash 冲突，还需要确保 haystack[left:right+1] 与 needle 相同
		if sha == target && haystack[left:right+1] == needle {
			return left
		}
		// 未匹配成功，left 右移一位
		sha = (sha - (int(haystack[left])*multi)%mod + mod) % mod
		left++
	}
	return -1
}

方法三：KMP 算法 · Go 实现

思考

方法二把窗口比较降到期望 $O(1)$，但仍依赖取模哈希，冲突时还要核对原串。我们希望最坏情况也是线性，且不引入哈希。

失配后不必把 $\mathit{\text{haystack}}$ 的指针退回起点。 $\mathit{\text{needle}}$ 的前缀函数给出“当前已匹配前缀的最长真后缀”，从而知道下一次该从模式串的哪一位继续。

先对 $\mathit{\text{needle}}$ 求 $\mathit{\text{next}}$，再单次扫描 $\mathit{\text{haystack}}$，失配只沿 $\mathit{\text{next}}$ 回退。时间 $O(n+m)$，额外空间 $O(m)$。

先对模式串 $\mathit{\text{needle}}$ 求前缀函数 $\mathit{\text{next}}$，其中 $\mathit{\text{next}}[i]$ 表示 $\mathit{\text{needle}}[0..i]$ 的最长真前后缀长度。随后在 $\mathit{\text{haystack}}$ 上扫描：字符相等则匹配长度加一，失配则令匹配长度跳到 $\mathit{\text{next}}[j-1]$。当匹配长度达到 $m$ 时，返回起始下标 $i-m+1$。

时间复杂度 $O(n+m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别为 $\mathit{\text{haystack}}$ 与 $\mathit{\text{needle}}$ 的长度。

func strStr(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	nxt := make([]int, m)
	for i, j := 1, 0; i < m; i++ {
		for j > 0 && needle[i] != needle[j] {
			j = nxt[j-1]
		}
		if needle[i] == needle[j] {
			j++
		}
		nxt[i] = j
	}
	for i, j := 0, 0; i < n; i++ {
		for j > 0 && haystack[i] != needle[j] {
			j = nxt[j-1]
		}
		if haystack[i] == needle[j] {
			j++
		}
		if j == m {
			return i - m + 1
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

31. 下一个排列

中等1 种解法

标签：数组、双指针

题目、示例与约束

整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

 

示例 1：

输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：

输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：

输入：nums = [1,1,5]
输出：[1,5,1]

 

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

方法一：两次遍历 · Go 实现

思考

若生成全部排列再取当前序列的后继，时间复杂度为 $O(n!)$。 $n\le 100$，无法通过，且题目要求原地修改、仅使用常数额外空间。

我们并不需要全集，只需字典序中紧邻的下一个。下一个排列必须严格大于当前序列，且改动应尽量靠右、幅度尽量小。

注意到，最长降序后缀已经是该段能排出的最大形态；它左侧的 $nums[i]$ 才是需要抬高的枢轴。后缀里刚好比 $nums[i]$ 大的数位于最右侧，交换后再将后缀翻成升序，改动便落在最右边。若整段均为降序，则不存在更大的排列，反转即回到最小排列。

我们先从后往前遍历数组 $nums$，找到第一个满足 $nums[i]<nums[i+1]$ 的位置 $i$，那么 $nums[i]$ 就是我们需要交换的元素，而 $nums[i+1]$ 到 $nums[n-1]$ 的元素是一个降序序列。

接下来，我们再从后往前遍历数组 $nums$，找到第一个满足 $nums[j]>nums[i]$ 的位置 $j$，然后我们交换 $nums[i]$ 和 $nums[j]$。最后，我们将 $nums[i+1]$ 到 $nums[n-1]$ 的元素反转，即可得到下一个排列。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组的长度。

func nextPermutation(nums []int) {
	n := len(nums)
	i := n - 2
	for ; i >= 0 && nums[i] >= nums[i+1]; i-- {
	}
	if i >= 0 {
		for j := n - 1; j > i; j-- {
			if nums[j] > nums[i] {
				nums[i], nums[j] = nums[j], nums[i]
				break
			}
		}
	}
	for j, k := i+1, n-1; j < k; j, k = j+1, k-1 {
		nums[j], nums[k] = nums[k], nums[j]
	}
}

力扣原题 · Doocs 题解来源

75. 颜色分类

中等1 种解法

标签：数组、双指针、冒泡排序、排序、快速排序

题目、示例与约束

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

 

示例 1：

输入：nums = [2,0,2,1,1,0]

输出：[0,0,1,1,2,2]

解释：

该数组包含两个 0、两个 1 和两个 2。将它们原地排序后，所有 0 排在最前面，接着是所有 1，最后是所有 2。

示例 2：

输入：nums = [2,0,1]

输出：[0,1,2]

解释：

数组中有且仅有一个 0、一个 1 和一个 2，按 0、1、2 的顺序原地排列。

 

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

 

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

方法一：三指针 · Go 实现

思考

统计 $0$、 $1$、 $2$ 的个数再覆写需要两趟扫描；直接排序也能得到结果， $n\le 300$ 时间足够。题目不允许使用库函数排序，进阶还要求一趟扫描且仅用常数额外空间。

数组中只有三个取值，需要划分成「全 $0$ / 全 $1$ / 全 $2$」三段。为此用 $i$、 $j$ 分别框住已经归位的 $0$ 与 $2$， $k$ 扫描未知区间。与 $2$ 交换时，换回来的元素尚未考察，因此 $k$ 不能前进；与 $0$ 交换时，换回来的元素来自已扫描区间，因此 $k$ 可以同步右移。一遍结束后三段自然有序。

我们定义三个指针 $i$, $j$ 和 $k$，其中指针 $i$ 用于指向数组中元素值为 $0$ 的最右边界，指针 $j$ 用于指向数组中元素值为 $2$ 的最左边界，初始时 $i=-1$, $j=n$。指针 $k$ 用于指向当前遍历的元素，初始时 $k=0$。

当 $k<j$ 时，我们执行如下操作：

• 若 $nums[k]=0$，则将其与 $nums[i+1]$ 交换，然后 $i$ 和 $k$ 都加 $1$；
• 若 $nums[k]=2$，则将其与 $nums[j-1]$ 交换，然后 $j$ 减 $1$；
• 若 $nums[k]=1$，则 $k$ 加 $1$。

遍历结束后，数组中的元素就被分成了 $[0,i]$, $[i+1,j-1]$ 和 $[j,n-1]$ 三个部分。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。只需要遍历一遍数组即可。空间复杂度 $O(1)$。

func sortColors(nums []int) {
	i, j, k := -1, len(nums), 0
	for k < j {
		if nums[k] == 0 {
			i++
			nums[i], nums[k] = nums[k], nums[i]
			k++
		} else if nums[k] == 2 {
			j--
			nums[j], nums[k] = nums[k], nums[j]
		} else {
			k++
		}
	}
}

力扣原题 · Doocs 题解来源

80. 删除有序数组中的重复项 II

中等1 种解法

标签：数组、双指针

题目、示例与约束

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

 

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

 

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

 

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按升序排列

方法一：一次遍历 · Go 实现

思考

另开数组、每个值最多抄写两次可以完成，但题目要求原地修改且额外空间为 $O(1)$。 $n\le 3\times {10}^4$，应当一趟完成。

由于数组有序，相同值必然相邻。问题 26 保留一次，本题保留至多两次。用 $k$ 表示已保留前缀的长度：当前值 $x$ 可以写入，当且仅当已保留不足两个，或它与倒数第二个保留值不同——否则即为第三次出现。写入 $nums[k]$ 后令 $k$ 加一，扫完返回 $k$。

我们用一个变量 $k$ 记录当前已经处理好的数组的长度，初始时 $k=0$，表示空数组。

然后我们从左到右遍历数组，对于遍历到的每个元素 $x$，如果 $k<2$ 或者 $x\ne nums[k-2]$，我们就将 $x$ 放到 $nums[k]$ 的位置，然后 $k$ 自增 $1$。否则， $x$ 与 $nums[k-2]$ 相同，我们直接跳过这个元素。继续遍历，直到遍历完整个数组。

这样，当遍历结束时， $nums$ 中前 $k$ 个元素就是我们要求的答案，且 $k$ 就是答案的长度。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组的长度。

补充：

原问题要求最多相同的数字最多出现 $2$ 次，我们可以扩展至相同的数字最多保留 $k$ 个。

• 由于相同的数字最多保留 $k$ 个，那么原数组的前 $k$ 个元素我们可以直接保留；
• 对于后面的数字，能够保留的前提是：当前数字 $x$ 与前面已保留的数字的倒数第 $k$ 个元素比较，不同则保留，相同则跳过。

相似题目：

• 26. 删除有序数组中的重复项

func removeDuplicates(nums []int) int {
	k := 0
	for _, x := range nums {
		if k < 2 || x != nums[k-2] {
			nums[k] = x
			k++
		}
	}
	return k
}

力扣原题 · Doocs 题解来源

88. 合并两个有序数组

简单1 种解法

标签：数组、双指针、排序

题目、示例与约束

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

 

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

 

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

 

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

方法一：双指针 · Go 实现

思考

另开数组、从前往后双指针合并再写回 $\mathit{\text{nums1}}$，结果正确。 $m+n\le 200$，时间没有压力，却要 $O(m+n)$ 额外空间，也不满足原地改写。

从前往后写会覆盖 $\mathit{\text{nums1}}$ 里尚未读出的数。空位却集中在尾部。因此可以从后往前：先放置当前较大者，不会踩到未处理元素。

用 $i$、 $j$ 分别扫两段有效末尾， $k$ 写合并后的末尾，直到 $\mathit{\text{nums2}}$ 耗尽即可。

我们注意到数组的有序性，可以使用双指针的方法，从后向前遍历两个数组，每次取两个数组中较大的一个放进合并后的数组的最后面。

具体地，我们用两个指针 $i$ 和 $j$ 分别指向两个数组的末尾，用一个指针 $k$ 指向合并后的数组的末尾。每次比较两个数组的末尾元素，将较大的元素放在合并后的数组的末尾，然后将指针向前移动一位，重复这个过程，直到两个数组的指针都指向了数组的开头。

时间复杂度 $O(m+n)$，其中 $m$ 和 $n$ 分别是两个数组的长度。空间复杂度 $O(1)$。

func merge(nums1 []int, m int, nums2 []int, n int) {
	for i, j, k := m-1, n-1, m+n-1; j >= 0; k-- {
		if i >= 0 && nums1[i] > nums2[j] {
			nums1[k] = nums1[i]
			i--
		} else {
			nums1[k] = nums2[j]
			j--
		}
	}
}

力扣原题 · Doocs 题解来源

125. 验证回文串

简单1 种解法

标签：双指针、字符串

题目、示例与约束

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

 

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

 

提示：

• 1 <= s.length <= 2 * 105
• s 仅由可打印的 ASCII 字符组成

方法一：双指针 · Go 实现

思考

判断忽略大小写与非字母数字后的串是否回文。先筛出合法字符再反转比较， $n\le 2\times {10}^5$ 时间可以，但要额外 $O(n)$ 空间。

回文只需对称位置相等。两端指针同时向中间走：遇到非法字符就跳过，合法字符则忽略大小写比较。一次扫描、常数空间即可。

我们用双指针 $i$ 和 $j$ 分别指向字符串 $s$ 的两端，接下来循环以下过程，直至 $i\ge j$：

1. 如果 $s[i]$ 不是字母或数字，指针 $i$ 右移一位，继续下一次循环；
2. 如果 $s[j]$ 不是字母或数字，指针 $j$ 左移一位，继续下一次循环；
3. 如果 $s[i]$ 和 $s[j]$ 的小写形式不相等，返回 false；
4. 否则，指针 $i$ 右移一位，指针 $j$ 左移一位，继续下一次循环。

循环结束，返回 true。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$。

func isPalindrome(s string) bool {
	i, j := 0, len(s)-1
	for i < j {
		if !isalnum(s[i]) {
			i++
		} else if !isalnum(s[j]) {
			j--
		} else if tolower(s[i]) != tolower(s[j]) {
			return false
		} else {
			i, j = i+1, j-1
		}
	}
	return true
}

func isalnum(ch byte) bool {
	return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')
}

func tolower(ch byte) byte {
	if ch >= 'A' && ch <= 'Z' {
		return ch + 32
	}
	return ch
}

力扣原题 · Doocs 题解来源

151. 反转字符串中的单词

中等2 种解法

标签：双指针、字符串

题目、示例与约束

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

 

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

 

提示：

• 1 <= s.length <= 104
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

 

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

方法一：双指针 · Go 实现

思考

要反转单词顺序并挤掉多余空格。 $n\le {10}^4$。用双指针扫描，跳过空格后截出每个单词，收集后再整体反转拼接，首尾与词间空格自然消失。

我们可以使用双指针 $i$ 和 $j$，每次找到一个单词，将其添加到结果列表中，最后将结果列表反转，再拼接成字符串即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串的长度。

func reverseWords(s string) string {
	words := []string{}
	i, n := 0, len(s)
	for i < n {
		for i < n && s[i] == ' ' {
			i++
		}
		if i < n {
			j := i
			t := []byte{}
			for j < n && s[j] != ' ' {
				t = append(t, s[j])
				j++
			}
			words = append(words, string(t))
			i = j
		}
	}
	for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
		words[i], words[j] = words[j], words[i]
	}
	return strings.Join(words, " ")
}

方法二：字符串分割 · Go 实现

思考

方法一手工切词。语言自带的按空白分割会丢掉多余空格，得到单词列表后再反转拼接，代码更短，复杂度相同。

我们可以使用语言内置的字符串分割函数，将字符串按空格分割成单词列表，然后将列表反转，再拼接成字符串即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串的长度。

func reverseWords(s string) string {
	words := strings.Fields(s)
	for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
		words[i], words[j] = words[j], words[i]
	}
	return strings.Join(words, " ")
}

力扣原题 · Doocs 题解来源

161. 相隔为 1 的编辑距离 🔒

中等1 种解法

标签：双指针、字符串

题目、示例与约束

给定两个字符串 s 和 t ，如果它们的编辑距离为 1 ，则返回 true ，否则返回 false 。

字符串 s 和字符串 t 之间满足编辑距离等于 1 有三种可能的情形：

• 往 s 中插入 恰好一个 字符得到 t
• 从 s 中删除 恰好一个 字符得到 t
• 在 s 中用 一个不同的字符 替换 恰好一个 字符得到 t

 

示例 1：

输入: s = "ab", t = "acb"
输出: true
解释: 可以将 'c' 插入字符串 s 来得到 t。

示例 2:

输入: s = "cab", t = "ad"
输出: false
解释: 无法通过 1 步操作使 s 变为 t。

 

提示:

• 0 <= s.length, t.length <= 104
• s 和 t 由小写字母，大写字母和数字组成

方法一：分情况讨论 · Go 实现

思考

判断能否用恰好一次插入、删除或替换把 $s$ 变成 $t$。长度差超过 $1$ 则不可能。 $n\le {10}^4$。先保证 $s$ 不短于 $t$，扫到第一处不同：等长则比较后面是否相同（替换），不等长则比较 $s$ 删掉该字符后是否等于 $t$ 剩余（删除）。全部相同则只能是 $s$ 恰好比 $t$ 多一个字符。

记 $m$ 表示字符串 $s$ 的长度， $n$ 表示字符串 $t$ 的长度。我们可以假定 $m$ 恒大于等于 $n$。

若 $m-n>1$，直接返回 false；

否则，遍历 $s$ 和 $t$，若遇到 $s[i]$ 不等于 $t[i]$：

• 若 $m\ne n$，比较 $s[i+1:]$ 与 $t[i:]$，相等返回 true，否则返回 false；
• 若 $m=n$，比较 $s[i:]$ 与 $t[i:]$，相等返回 true，否则返回 false。

遍历结束，说明遍历过的 $s$ 跟 $t$ 所有字符相等，此时需要满足 $m=n+1$。

时间复杂度 $O(m)$，其中 $m$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。

func isOneEditDistance(s string, t string) bool {
	m, n := len(s), len(t)
	if m < n {
		return isOneEditDistance(t, s)
	}
	if m-n > 1 {
		return false
	}
	for i := range t {
		if s[i] != t[i] {
			if m == n {
				return s[i+1:] == t[i+1:]
			}
			return s[i+1:] == t[i:]
		}
	}
	return m == n+1
}

力扣原题 · Doocs 题解来源

165. 比较版本号

中等1 种解法

标签：双指针、字符串

题目、示例与约束

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。

比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

返回规则如下：

• 如果 version1 < version2 返回 -1，
• 如果 version1 > version2 返回 1，
• 除此之外返回 0。

 

示例 1：

输入：version1 = "1.2", version2 = "1.10"

输出：-1

解释：

version1 的第二个修订号为 "2"，version2 的第二个修订号为 "10"：2 < 10，所以 version1 < version2。

示例 2：

输入：version1 = "1.01", version2 = "1.001"

输出：0

解释：

忽略前导零，"01" 和 "001" 都代表相同的整数 "1"。

示例 3：

输入：version1 = "1.0", version2 = "1.0.0.0"

输出：0

解释：

version1 有更少的修订号，每个缺失的修订号按 "0" 处理。

 

提示：

• 1 <= version1.length, version2.length <= 500
• version1 和 version2 仅包含数字和 '.'
• version1 和 version2 都是 有效版本号
• version1 和 version2 的所有修订号都可以存储在 32 位整数 中

方法一：双指针 · Go 实现

思考

按修订号逐段比较，缺省段视为 $0$，前导零不影响数值。拆成整数数组再比较要额外空间。长度不超过 $500$，双指针同步扫，遇到点就结算当前段，较短的一侧用 $0$ 补齐，直到分出大小或两端结束。

同时遍历两个字符串，用两个指针 $i$ 和 $j$ 分别指向两个字符串的当前位置，初始时 $i=j=0$。

每次取出两个字符串中对应的修订号，记为 $a$ 和 $b$，比较 $a$ 和 $b$ 的大小，如果 $a<b$，则返回 $-1$；如果 $a>b$，则返回 $1$；如果 $a=b$，则继续比较下一对修订号。

时间复杂度 $O(max(m,n))$，空间复杂度 $O(1)$。其中 $m$ 和 $n$ 分别是两个字符串的长度。

func compareVersion(version1 string, version2 string) int {
	m, n := len(version1), len(version2)
	for i, j := 0, 0; i < m || j < n; i, j = i+1, j+1 {
		var a, b int
		for i < m && version1[i] != '.' {
			a = a*10 + int(version1[i]-'0')
			i++
		}
		for j < n && version2[j] != '.' {
			b = b*10 + int(version2[j]-'0')
			j++
		}
		if a < b {
			return -1
		}
		if a > b {
			return 1
		}
	}
	return 0
}

力扣原题 · Doocs 题解来源

186. 反转字符串中的单词 II 🔒

中等1 种解法

标签：双指针、字符串

题目、示例与约束

给你一个字符数组 s ，反转其中 单词 的顺序。

单词 的定义为：单词是一个由非空格字符组成的序列。s 中的单词将会由单个空格分隔。

必须设计并实现 原地 解法来解决此问题，即不分配额外的空间。

 

示例 1：

输入：s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出：["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

示例 2：

输入：s = ["a"]
输出：["a"]

 

提示：

• 1 <= s.length <= 105
• s[i] 可以是一个英文字母（大写或小写）、数字、或是空格 ' ' 。
• s 中至少存在一个单词
• s 不含前导或尾随空格
• 题目数据保证：s 中的每个单词都由单个空格分隔

方法一：双指针 · Go 实现

思考

字符数组上原地反转单词顺序，词间恰有一个空格，无首尾空格。 $n\le {10}^5$，额外 $O(1)$ 空间。先反转每个单词，再反转整个数组，单词顺序颠倒而词内字符恢复正向。双指针框住每个词的左右端。

我们可以遍历字符数组 $s$，利用双指针 $i$ 和 $j$ 找到每个单词的起始位置和结束位置，然后反转每个单词，最后再反转整个字符数组。

时间复杂度 $O(n)$，其中 $n$ 为字符数组 $s$ 的长度。空间复杂度 $O(1)$。

func reverseWords(s []byte) {
	reverse := func(i, j int) {
		for ; i < j; i, j = i+1, j-1 {
			s[i], s[j] = s[j], s[i]
		}
	}
	i, n := 0, len(s)
	for j, c := range s {
		if c == ' ' {
			reverse(i, j-1)
			i = j + 1
		} else if j == n-1 {
			reverse(i, j)
		}
	}
	reverse(0, n-1)
}

力扣原题 · Doocs 题解来源

189. 轮转数组

中等1 种解法

标签：数组、数学、双指针

题目、示例与约束

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

 

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

 

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

 

进阶：

• 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

方法一：三次翻转 · Go 实现

思考

右旋 $k$ 步。开新数组再拷回是 $O(n)$ 空间； $n\le {10}^5$，进阶要原地。右旋 $k$ 位等于「后 $k$ 个移到前面」。整体反转后，前 $k$ 与后 $n-k$ 再各自反转，三段翻转完成轮换，只交换元素。

我们不妨记数组长度为 $n$，然后将 $k$ 对 $n$ 取模，得到实际需要旋转的步数 $k$。

接下来，我们进行三次翻转，即可得到最终结果：

1. 将整个数组翻转
2. 将前 $k$ 个元素翻转
3. 将后 $n-k$ 个元素翻转

举个例子，对于数组 $[1,2,3,4,5,6,7]$, $k=3$, $n=7$, $kmodn=3$。

1. 第一次翻转，将整个数组翻转，得到 $[7,6,5,4,3,2,1]$。
2. 第二次翻转，将前 $k$ 个元素翻转，得到 $[5,6,7,4,3,2,1]$。
3. 第三次翻转，将后 $n-k$ 个元素翻转，得到 $[5,6,7,1,2,3,4]$，即为最终结果。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

func rotate(nums []int, k int) {
	n := len(nums)
	k %= n
	reverse := func(i, j int) {
		for ; i < j; i, j = i+1, j-1 {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	reverse(0, n-1)
	reverse(0, k-1)
	reverse(k, n-1)
}

力扣原题 · Doocs 题解来源

202. 快乐数

简单2 种解法

标签：哈希表、数学、双指针、Floyd 判圈算法

题目、示例与约束

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

 

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

 

提示：

• 1 <= n <= 231 - 1

方法一：哈希表 + 模拟 · Go 实现

思考

按定义反复取各位平方和即可判定，但序列既可能到达 $1$，也可能陷入循环。平方和会迅速落入有限范围，因此可用哈希表记录出现过的数。

若再现则存在环、不是快乐数；若变为 $1$ 则是。模拟与判重同步进行，空间与值域规模相当。

将每次转换后的数字存入哈希表，如果出现重复数字，说明进入了循环，不是快乐数。否则，如果转换后的数字为 $1$，说明是快乐数。

时间复杂度 $O(\log n)$，空间复杂度 $O(\log n)$。

func isHappy(n int) bool {
	vis := map[int]bool{}
	for n != 1 && !vis[n] {
		vis[n] = true
		x := 0
		for ; n > 0; n /= 10 {
			x += (n % 10) * (n % 10)
		}
		n = x
	}
	return n == 1
}

方法二：快慢指针 · Go 实现

思考

方法一已能正确判定，但哈希表占用额外空间。平方和变换是确定的函数迭代，环检测不必存全部历史。

为此用快慢指针：慢指针走一步、快指针走两步，相遇时若值为 $1$ 则是快乐数，从而将空间降为常数。

与判断链表是否存在环原理一致。如果 $n$ 是快乐数，那么快指针最终会与慢指针相遇，且相遇时的数字为 $1$；否则，快指针最终会与慢指针相遇，且相遇时的数字不为 $1$。

因此，最后判断快慢指针相遇时的数字是否为 $1$ 即可。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

func isHappy(n int) bool {
	next := func(x int) (y int) {
		for ; x > 0; x /= 10 {
			y += (x % 10) * (x % 10)
		}
		return
	}
	slow, fast := n, next(n)
	for slow != fast {
		slow = next(slow)
		fast = next(next(fast))
	}
	return slow == 1
}

力扣原题 · Doocs 题解来源

246. 中心对称数 🔒

简单1 种解法

标签：哈希表、双指针、字符串

题目、示例与约束

中心对称数是指一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

请写一个函数来判断该数字是否是中心对称数，其输入将会以一个字符串的形式来表达数字。

 

示例 1:

输入: num = "69"
输出: true

示例 2:

输入: num = "88"
输出: true

示例 3:

输入: num = "962"
输出: false

示例 4：

输入：num = "1"
输出：true

方法一：双指针模拟 · Go 实现

思考

中心对称要求旋转 ${180}^{\circ }$ 后仍是原数，只有 $0,1,8$ 不变， $6$ 与 $9$ 互换。从两端向中间检查映射是否匹配。

我们定义一个数组 $d$，其中 $d[i]$ 表示数字 $i$ 旋转 180° 之后的数字。如果 $d[i]$ 为 $-1$，表示数字 $i$ 不能旋转 180° 得到一个数字。

定义两个指针 $i$ 和 $j$，分别指向字符串的左右两端，然后不断向中间移动指针，判断 $d[num[i]]$ 和 $num[j]$ 是否相等，如果不相等，说明该字符串不是中心对称数，直接返回 $false$ 即可。如果 $i>j$，说明遍历完了字符串，返回 $true$。

时间复杂度 $O(n)$，其中 $n$ 为字符串的长度。空间复杂度 $O(1)$。

func isStrobogrammatic(num string) bool {
	d := []int{0, 1, -1, -1, -1, -1, 9, -1, 8, 6}
	for i, j := 0, len(num)-1; i <= j; i, j = i+1, j-1 {
		a, b := int(num[i]-'0'), int(num[j]-'0')
		if d[a] != b {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

283. 移动零

简单1 种解法

标签：数组、双指针

题目、示例与约束

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

 

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

 

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

 

进阶：你能尽量减少完成的操作次数吗？

方法一：双指针 · Go 实现

思考

要把 $0$ 移到末尾且保持非零相对次序，可用双指针： $k$ 指向下一个非零应放的位置。

遇到非零就与 $nums[k]$ 交换并右移 $k$，则前 $k$ 位为原相对顺序的非零。

我们用一个指针 $k$ 记录当前待插入的位置，初始时 $k=0$。

然后我们遍历数组 $\mathit{\text{nums}}$，每次遇到一个非零数，就将其与 $\mathit{\text{nums}}[k]$ 交换，同时将 $k$ 的值加 $1$。

这样我们就可以保证 $\mathit{\text{nums}}$ 的前 $k$ 个元素都是非零的，且它们的相对顺序与原数组一致。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func moveZeroes(nums []int) {
	k := 0
	for i, x := range nums {
		if x != 0 {
			nums[i], nums[k] = nums[k], nums[i]
			k++
		}
	}
}

力扣原题 · Doocs 题解来源

344. 反转字符串

简单1 种解法

标签：双指针、字符串

题目、示例与约束

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

 

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

 

提示：

• 1 <= s.length <= 105
• s[i] 都是 ASCII 码表中的可打印字符

方法一：双指针 · Go 实现

思考

原地反转字符数组。额外数组再写回需 $O(n)$ 空间。首尾交换即可。

双指针 $i,j$ 分别从两端逼近，交换后相向移动直至相遇。一次扫描、常数空间。

我们用两个指针 $i$ 和 $j$，初始时分别指向数组的首尾，每次将 $i$ 和 $j$ 对应的元素交换，然后 $i$ 向后移动， $j$ 向前移动，直到 $i$ 和 $j$ 相遇。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

func reverseString(s []byte) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

力扣原题 · Doocs 题解来源

345. 反转字符串中的元音字母

简单1 种解法

标签：双指针、字符串

题目、示例与约束

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

 

示例 1：

输入：s = "IceCreAm"

输出："AceCreIm"

解释：

s 中的元音是 ['I', 'e', 'e', 'A']。反转这些元音，s 变为 "AceCreIm".

示例 2：

输入：s = "leetcode"

输出："leotcede"

 

提示：

• 1 <= s.length <= 3 * 105
• s 由 可打印的 ASCII 字符组成

方法一：双指针 · Go 实现

思考

只反转元音，辅音位置不动。抽出元音再写回需额外数组。与反转整串相同，但只在元音上交换。

两端指针跳过非元音，相遇前交换，再继续收缩。元音集合用字符串（或集合）判定大小写。

我们可以用两个指针 $i$ 和 $j$，初始时分别指向字符串的首尾。

每次循环判断 $i$ 指向的字符是否是元音字母，如果不是则向后移动 $i$；同理，判断 $j$ 指向的字符是否是元音字母，如果不是则向前移动 $j$。如果此时 $i<j$，那么 $i$ 和 $j$ 指向的字符都是元音字母，交换这两个字符。然后向后移动 $i$，向前移动 $j$。继续上述操作，直到 $i\ge j$。

时间复杂度 $O(n)$，其中 $n$ 是字符串的长度。空间复杂度 $O(|\mathrm{\Sigma }|)$，其中 $\mathrm{\Sigma }$ 是字符集的大小。

func reverseVowels(s string) string {
	vowels := [128]bool{}
	for _, c := range "aeiouAEIOU" {
		vowels[c] = true
	}
	cs := []byte(s)
	i, j := 0, len(cs)-1
	for i < j {
		for i < j && !vowels[cs[i]] {
			i++
		}
		for i < j && !vowels[cs[j]] {
			j--
		}
		if i < j {
			cs[i], cs[j] = cs[j], cs[i]
			i, j = i+1, j-1
		}
	}
	return string(cs)
}

力扣原题 · Doocs 题解来源

360. 有序转化数组 🔒

中等1 种解法

标签：数组、数学、双指针、排序

题目、示例与约束

给你一个已经 排好序 的整数数组 nums 和整数 a 、 b 、 c 。对于数组中的每一个元素 nums[i] ，计算函数值 f(x) = ax2 + bx + c ，请 按升序返回数组 。

 

示例 1：

输入: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
输出: [3,9,15,33]

示例 2：

输入: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
输出: [-23,-5,1,7]

 

提示：

• 1 <= nums.length <= 200
• -100 <= nums[i], a, b, c <= 100
• nums 按照 升序排列

 

进阶：你可以在时间复杂度为 O(n) 的情况下解决这个问题吗？

方法一：数学 + 双指针 · Go 实现

思考

$nums$ 已排序，对 $a{x}^2+bx+c$ 后再排序。直接计算再 $O(n\log n)$ 排序即可，但二次函数在有序定义域上单调性已知。

$a>0$ 开口向上，两端较大，从答案尾部填较大值； $a\le 0$ 则两端较小，从头部填较小值。双指针向内收，一次线性完成。

根据数学知识可知，二次函数的图像是一条抛物线，当 $a>0$ 时，抛物线开口向上，顶点为最小值；当 $a<0$ 时，抛物线开口向下，顶点为最大值。

由于数组 $\mathit{\text{nums}}$ 已经排好序，我们可以使用双指针分别指向数组的两端，根据 $a$ 的正负决定从结果数组的头部还是尾部开始填充较大（或较小）的值。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。

func sortTransformedArray(nums []int, a int, b int, c int) []int {
	f := func(x int) int {
		return a*x*x + b*x + c
	}

	n := len(nums)
	ans := make([]int, n)
	i, j := 0, n-1

	for k := 0; k < n; k++ {
		y1, y2 := f(nums[i]), f(nums[j])
		if a > 0 {
			if y1 > y2 {
				ans[n-k-1] = y1
				i++
			} else {
				ans[n-k-1] = y2
				j--
			}
		} else {
			if y1 > y2 {
				ans[k] = y2
				j--
			} else {
				ans[k] = y1
				i++
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

408. 有效单词缩写 🔒

简单1 种解法

标签：双指针、字符串

题目、示例与约束

字符串可以用 缩写 进行表示，缩写 的方法是将任意数量的 不相邻 的子字符串替换为相应子串的长度。例如，字符串 "substitution" 可以缩写为（不止这几种方法）：

• "s10n" ("s ubstitutio n")
• "sub4u4" ("sub stit u tion")
• "12" ("substitution")
• "su3i1u2on" ("su bst i t u ti on")
• "substitution" (没有替换子字符串)

下列是不合法的缩写：

• "s55n" ("s ubsti tutio n"，两处缩写相邻)
• "s010n" (缩写存在前导零)
• "s0ubstitution" (缩写是一个空字符串)

给你一个字符串单词 word 和一个缩写 abbr ，判断这个缩写是否可以是给定单词的缩写。

子字符串是字符串中连续的非空字符序列。

 

示例 1：

输入：word = "internationalization", abbr = "i12iz4n"
输出：true
解释：单词 "internationalization" 可以缩写为 "i12iz4n" ("i nternational iz atio n") 。

示例 2：

输入：word = "apple", abbr = "a2e"
输出：false
解释：单词 "apple" 无法缩写为 "a2e" 。

 

提示：

• 1 <= word.length <= 20
• word 仅由小写英文字母组成
• 1 <= abbr.length <= 10
• abbr 由小写英文字母和数字组成
• abbr 中的所有数字均符合 32-bit 整数范围

方法一：模拟 · Go 实现

思考

缩写由字母与数字交错组成，数字表示跳过的长度，且不能有前导零。若先把缩写展开再比较，数字可能很大，不必真的构造新串。

双指针扫描 $\mathit{\text{abbr}}$：遇数字则累加跳过长度并拒绝前导零；遇字母时先跳过再比对字符。结束时 $\mathit{\text{word}}$ 指针加上剩余跳过应恰好到末尾。

跳过与比对必须在同一趟完成，才能同时检查越界、失配与长度是否用尽。

我们可以直接模拟字符匹配替换。

假设字符串 $word$ 和字符串 $abbr$ 的长度分别为 $m$ 和 $n$，我们使用两个指针 $i$ 和 $j$ 分别指向字符串 $word$ 和字符串 $abbr$ 的初始位置，用一个整型变量 $x$ 记录当前匹配到的 $abbr$ 的数字。

循环匹配字符串 $word$ 和字符串 $abbr$ 的每个字符：

如果指针 $j$ 指向的字符 $abbr[j]$ 是数字，如果 $abbr[j]$ 是 '0'，并且 $x$ 为 $0$，说明 $abbr$ 中的数字含有前导零，因此不是合法的缩写，返回 false；否则将 $x$ 更新为 $x\times 10+abbr[j]{-}^{\prime }{0}^{\prime }$。

如果指针 $j$ 指向的字符 $abbr[j]$ 不是数字，那么我们此时将指针 $i$ 往前移动 $x$ 个位置，然后将 $x$ 重置为 $0$。如果此时 $i\ge m$ 或者 $word[i]\ne abbr[j]$，说明两个字符串无法匹配，返回 false；否则将指针 $i$ 往前移动 $1$ 个位置。

然后我们将指针 $j$ 往前移动 $1$ 个位置，重复上述过程，直到 $i$ 超出字符串 $word$ 的长度或者 $j$ 超出字符串 $abbr$ 的长度。

最后，如果 $i+x$ 等于 $m$ 且 $j$ 等于 $n$，说明字符串 $word$ 可以缩写成字符串 $abbr$，返回 true；否则返回 false。

时间复杂度 $O(m+n)$，其中 $m$ 和 $n$ 分别是字符串 $word$ 和字符串 $abbr$ 的长度。空间复杂度 $O(1)$。

func validWordAbbreviation(word string, abbr string) bool {
	m, n := len(word), len(abbr)
	i, j, x := 0, 0, 0
	for ; i < m && j < n; j++ {
		if abbr[j] >= '0' && abbr[j] <= '9' {
			if x == 0 && abbr[j] == '0' {
				return false
			}
			x = x*10 + int(abbr[j]-'0')
		} else {
			i += x
			x = 0
			if i >= m || word[i] != abbr[j] {
				return false
			}
			i++
		}
	}
	return i+x == m && j == n
}

力扣原题 · Doocs 题解来源

443. 压缩字符串

中等1 种解法

标签：双指针、字符串

题目、示例与约束

给你一个字符数组 chars ，请使用下述算法压缩：

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：

• 如果这一组长度为 1 ，则将字符追加到 s 中。
• 否则，需要向 s 追加字符，后跟这一组的长度。

压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在 修改完输入数组后 ，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。

注意：数组中超出返回长度的字符无关紧要，应予忽略。

 

示例 1：

输入：chars = ["a","a","b","b","c","c","c"]
输出：6
解释：分组是 "aa"、"bb" 和 "ccc"，压缩为 "a2b2c3"。
在原地修改输入数组之后，chars 的前 6 个字符应为 ["a","2","b","2","c","3"]。

示例 2：

输入：chars = ["a"]
输出：1
解释：唯一的组是 "a"，因为它是一个单独的字符，所以保持不变。
在原地修改输入数组后，chars 的第一个字符应为 ["a"]。

示例 3：

输入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：4
解释：分组是 "a" 和 "bbbbbbbbbbbb"，压缩为"ab12"。
在对输入数组进行原地修改后，chars 的前 4 个字符应为 ["a","b","1","2"]。

 

提示：

• 1 <= chars.length <= 2000
• chars[i] 可以是小写英文字母、大写英文字母、数字或符号

方法一 · Go 实现

思考

连续相同字符要写成字符加次数（次数大于 $1$ 时），且必须原地写回。另开字符串再拷贝违反空间要求。

读指针 $i$ 找一段相同字符，写指针 $k$ 先写字符，长度大于 $1$ 再写十进制各位。 $i$ 跳到下一段。

写指针不超越读指针：压缩后长度不超过原长，从左覆盖是安全的。返回 $k$ 作为新长度。

func compress(chars []byte) int {
	i, k, n := 0, 0, len(chars)
	for i < n {
		j := i + 1
		for j < n && chars[j] == chars[i] {
			j++
		}
		chars[k] = chars[i]
		k++
		if j-i > 1 {
			cnt := strconv.Itoa(j - i)
			for _, c := range cnt {
				chars[k] = byte(c)
				k++
			}
		}
		i = j
	}
	return k
}

力扣原题 · Doocs 题解来源

457. 环形数组是否存在循环

中等1 种解法

标签：数组、哈希表、双指针、Floyd 判圈算法

题目、示例与约束

存在一个不含 0 的 环形 数组 nums ，每个 nums[i] 都表示位于下标 i 的角色应该向前或向后移动的下标个数：

• 如果 nums[i] 是正数，向前（下标递增方向）移动 nums[i] 步
• 如果 nums[i] 是负数，向后（下标递减方向）移动 abs(nums[i]) 步

因为数组是 环形 的，所以可以假设从最后一个元素向前移动一步会到达第一个元素，而第一个元素向后移动一步会到达最后一个元素。

数组中的 循环 由长度为 k 的下标序列 seq 标识：

• 遵循上述移动规则将导致一组重复下标序列 seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...
• 所有 nums[seq[j]] 应当不是 全正 就是 全负
• k > 1

如果 nums 中存在循环，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [2,-1,1,2,2]
输出：true
解释：图片展示了节点间如何连接。白色节点向前跳跃，而红色节点向后跳跃。
我们可以看到存在循环，按下标 0 -> 2 -> 3 -> 0 --> ...，并且其中的所有节点都是白色（以相同方向跳跃）。

示例 2：

输入：nums = [-1,-2,-3,-4,-5,6]
输出：false
解释：图片展示了节点间如何连接。白色节点向前跳跃，而红色节点向后跳跃。
唯一的循环长度为 1，所以返回 false。

示例 3：

输入：nums = [1,-1,5,1,4]
输出：true
解释：图片展示了节点间如何连接。白色节点向前跳跃，而红色节点向后跳跃。
我们可以看到存在循环，按下标 0 --> 1 --> 0 --> ...，当它的大小大于 1 时，它有一个向前跳的节点和一个向后跳的节点，所以 它不是一个循环。
我们可以看到存在循环，按下标 3 --> 4 --> 3 --> ...，并且其中的所有节点都是白色（以相同方向跳跃）。

 

提示：

• 1 <= nums.length <= 5000
• -1000 <= nums[i] <= 1000
• nums[i] != 0

 

进阶：你能设计一个时间复杂度为 O(n) 且额外空间复杂度为 O(1) 的算法吗？

方法一 · Go 实现

思考

在环形数组上按步长跳，求是否存在长度大于 $1$ 的同向环。记录整条路径集合需要额外空间，且 $n$ 不大但要排除自环与变向。

对每个起点快慢指针同向追逐：符号乘积为正保证同向。相遇后若下一步不是自身则找到环。沿途走过的位置置 $0$，之后不再作为起点。

置 $0$ 相当于染色，避免在无环链上反复出发；自环用 $\mathit{\text{slow}}\ne \mathit{\text{next}}(\mathit{\text{slow}})$ 排除。

func circularArrayLoop(nums []int) bool {
	for i, num := range nums {
		if num == 0 {
			continue
		}
		slow, fast := i, next(nums, i)
		for nums[slow]*nums[fast] > 0 && nums[slow]*nums[next(nums, fast)] > 0 {
			if slow == fast {
				if slow != next(nums, slow) {
					return true
				}
				break
			}
			slow, fast = next(nums, slow), next(nums, next(nums, fast))
		}
		j := i
		for nums[j]*nums[next(nums, j)] > 0 {
			nums[j] = 0
			j = next(nums, j)
		}
	}
	return false
}

func next(nums []int, i int) int {
	n := len(nums)
	return (i + nums[i]%n + n) % n
}

力扣原题 · Doocs 题解来源

481. 神奇字符串

中等1 种解法

标签：双指针、字符串

题目、示例与约束

神奇字符串 s 仅由 '1' 和 '2' 组成，并需要遵守下面的规则：

• 将连续相同字符组 '1' 和 '2' 长度的序列连接起来会生成字符串 s 本身。

s 的前几个元素是 s = "1221121221221121122……" 。如果将 s 中连续的若干 1 和 2 进行分组，可以得到 "1 22 11 2 1 22 1 22 11 2 11 22 ......" 。每组中 1 或者 2 的出现次数分别是 "1 2 2 1 1 2 1 2 2 1 2 2 ......" 。上面的出现次数正是 s 自身。

给你一个整数 n ，返回在神奇字符串 s 的前 n 个数字中 1 的数目。

 

示例 1：

输入：n = 6
输出：3
解释：神奇字符串 s 的前 6 个元素是 “122112”，它包含三个 1，因此返回 3 。 

示例 2：

输入：n = 1
输出：1

 

提示：

• 1 <= n <= 105

方法一：模拟构造过程 · Go 实现

思考

魔术串由自身的游程长度描述：第一组一个 $1$，第二组两个 $2$，之后 $1$ 与 $2$ 交替，组大小由串本身给出。要求前 $n$ 位中 $1$ 的个数。

从已知前缀 $122$ 出发，指针 $i$ 指向「下一组该出现几次」，末位决定下一组是 $1$ 还是 $2$（用 $3-\mathit{\text{pre}}$ 翻转），直到长度达到 $n$。

构造与计数同一趟完成。组大小读的是已经写下的字符，因此指针 $i$ 不会超过当前长度。

根据题目，我们得知，字符串 $s$ 的每一组数字都可以由字符串 $s$ 自身的数字得到。

字符串 $s$ 前两组数字为 $1$ 和 $22$，是由字符串 $s$ 的第一个数字 $1$ 和第二个数字 $2$ 得到的，并且第一组数字只包含 $1$，第二组数字只包含 $2$，第三组数字只包含 $1$，以此类推。

由于前两组数字已知，我们初始化字符串 $s$ 为 $122$，然后从第三组开始构造，第三组数字是由字符串 $s$ 的第三个数字（下标 $i=2$）得到，因此我们此时将指针 $i$ 指向字符串 $s$ 的第三个数字 $2$。

1 2 2
    ^
    i

指针 $i$ 指向的数字为 $2$，表示第三组的数字会出现两次，并且，由于前一组数字为 $2$，组之间数字交替出现，因此第三组数字为两个 $1$，即 $11$。构造后，指针 $i$ 移动到下一个位置，即指向字符串 $s$ 的第四个数字 $1$。

1 2 2 1 1
      ^
      i

这时候指针 $i$ 指向的数字为 $1$，表示第四组的数字会出现一次，并且，由于前一组数字为 $1$，组之间数字交替出现，因此第四组数字为一个 $2$，即 $2$。构造后，指针 $i$ 移动到下一个位置，即指向字符串 $s$ 的第五个数字 $1$。

1 2 2 1 1 2
        ^
        i

我们按照这个规则，依次模拟构造过程，直到字符串 $s$ 的长度大于等于 $n$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

func magicalString(n int) (ans int) {
	s := []int{1, 2, 2}
	for i := 2; len(s) < n; i++ {
		pre := s[len(s)-1]
		cur := 3 - pre
		for j := 0; j < s[i]; j++ {
			s = append(s, cur)
		}
	}
	for _, c := range s[:n] {
		if c == 1 {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

522. 最长特殊序列 II

中等1 种解法

标签：数组、哈希表、双指针、字符串、排序

题目、示例与约束

给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。

特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。

 s 的 子序列可以通过删去字符串 s 中的某些字符实现。

• 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)。

 

示例 1：

输入: strs = ["aba","cdc","eae"]
输出: 3

示例 2:

输入: strs = ["aaa","aaa","aa"]
输出: -1

 

提示:

• 2 <= strs.length <= 50
• 1 <= strs[i].length <= 10
• strs[i] 只包含小写英文字母

方法一：判断子序列 · Go 实现

思考

多串情形下，较长串仍可能是另一串的子序列，不能再只比长度。 $n\le 50$ 且串长短，枚举每个串判断它是否为其余串的子序列是可行的。

双指针检查 $s$ 是否为 $t$ 的子序列。若某个 $s$ 不是任何其他串的子序列，它就是独有的，用其长度更新答案。全部都是别人的子序列则返回 $-1$。

我们定义一个函数 $check(s,t)$，用于判断字符串 $s$ 是否是字符串 $t$ 的子序列。我们可以使用双指针的方法，初始化两个指针 $i$ 和 $j$ 分别指向字符串 $s$ 和字符串 $t$ 的开头，然后不断移动指针 $j$，如果 $s[i]$ 和 $t[j]$ 相等，则移动指针 $i$，最后判断 $i$ 是否等于 $s$ 的长度即可。若 $i$ 等于 $s$ 的长度，则说明 $s$ 是 $t$ 的子序列。

判断字符串 $s$ 是否独有，只需要取字符串 $s$ 本身，与字符串列表的其他字符串比较即可。如果存在 $s$ 是其他字符串的子序列，则 $s$ 不是独有的。否则，字符串 $s$ 是独有的。我们取所有独有字符串中长度最长的字符串即可。

时间复杂度 $O(n^2\times m)$，其中 $n$ 是字符串列表的长度，而 $m$ 是字符串的平均长度。空间复杂度 $O(1)$。

func findLUSlength(strs []string) int {
	ans := -1
	check := func(s, t string) bool {
		m, n := len(s), len(t)
		i := 0
		for j := 0; i < m && j < n; j++ {
			if s[i] == t[j] {
				i++
			}
		}
		return i == m
	}
	for i, s := range strs {
		x := len(s)
		for j, t := range strs {
			if i != j && check(s, t) {
				x = -1
				break
			}
		}
		ans = max(ans, x)
	}
	return ans
}

力扣原题 · Doocs 题解来源

524. 通过删除字母匹配到字典里最长单词

中等1 种解法

标签：数组、双指针、字符串、排序

题目、示例与约束

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

 

示例 1：

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

示例 2：

输入：s = "abpcplea", dictionary = ["a","b","c"]
输出："a"

 

提示：

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s 和 dictionary[i] 仅由小写英文字母组成

方法一：判断子序列 · Go 实现

思考

要从字典里选一个可通过删除 $s$ 中字符得到的最长串，并列时取字典序最小。对 $s$ 的每个子序列查字典不现实。

反过来对字典中每个词判断它是否为 $s$ 的子序列，双指针一次扫描即可。同时用长度优先、字典序其次的规则维护当前最优。字典大小与词长均不大，总代价可接受。

我们定义一个函数 $check(s,t)$，用于判断字符串 $s$ 是否是字符串 $t$ 的子序列。我们可以使用双指针的方法，初始化两个指针 $i$ 和 $j$ 分别指向字符串 $s$ 和字符串 $t$ 的开头，然后不断移动指针 $j$，如果 $s[i]$ 和 $t[j]$ 相等，则移动指针 $i$，最后判断 $i$ 是否等于 $s$ 的长度即可。若 $i$ 等于 $s$ 的长度，则说明 $s$ 是 $t$ 的子序列。

我们初始化答案字符串 $ans$ 为空字符串，然后遍历数组 $dictionary$ 中的每个字符串 $t$，如果 $t$ 是 $s$ 的子序列，并且 $t$ 的长度大于 $ans$ 的长度，或者 $t$ 的长度等于 $ans$ 的长度且 $t$ 字典序小于 $ans$，则更新 $ans$ 为 $t$。

时间复杂度 $O(d\times (m+n))$，其中 $d$ 是字符串列表的长度，而 $m$ 和 $n$ 分别是字符串 $s$ 的长度和字符串列表中字符串的平均长度。空间复杂度 $O(1)$。

func findLongestWord(s string, dictionary []string) string {
	ans := ""
	check := func(s, t string) bool {
		m, n := len(s), len(t)
		i := 0
		for j := 0; i < m && j < n; j++ {
			if s[i] == t[j] {
				i++
			}
		}
		return i == m
	}
	for _, t := range dictionary {
		a, b := len(ans), len(t)
		if check(t, s) && (a < b || (a == b && ans > t)) {
			ans = t
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

541. 反转字符串 II

简单1 种解法

标签：双指针、字符串

题目、示例与约束

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符，再重新计数。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

 

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

 

提示：

• 1 <= s.length <= 104
• s 仅由小写英文组成
• 1 <= k <= 104

方法一：双指针 · Go 实现

思考

每 $2k$ 个字符中，只反转前 $k$ 个。直接按块处理即可，无需复杂结构。

把字符串转成数组，步长 $2k$ 切片反转前 $k$ 个字符。最后一块不足 $k$ 时，切片会自然截断。拼回字符串即得。

我们可以遍历字符串 $\mathit{\text{s}}$，每次遍历 $\mathit{\text{2k}}$ 个字符，然后利用双指针技巧，对这 $\mathit{\text{2k}}$ 个字符中的前 $\mathit{\text{k}}$ 个字符进行反转。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $\mathit{\text{s}}$ 的长度。

func reverseStr(s string, k int) string {
	cs := []byte(s)
	n := len(cs)
	for i := 0; i < n; i += 2 * k {
		for l, r := i, min(i+k-1, n-1); l < r; l, r = l+1, r-1 {
			cs[l], cs[r] = cs[r], cs[l]
		}
	}
	return string(cs)
}

力扣原题 · Doocs 题解来源

556. 下一个更大元素 III

中等1 种解法

标签：数学、双指针、字符串

题目、示例与约束

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

 

示例 1：

输入：n = 12
输出：21

示例 2：

输入：n = 21
输出：-1

 

提示：

• 1 <= n <= 231 - 1

方法一：双指针 · Go 实现

思考

要找比 $n$ 大的最小整数，且所用数字是 $n$ 的一个排列。下一个排列算法正好做这件事。

从右找第一个下降位置 $i$（ $cs[i]<cs[i+1]$），再从右找刚好比 $cs[i]$ 大的 $j$，交换后把 $i$ 右侧反转成升序。若不存在下降位置则已是最大排列，返回 $-1$。结果超出 $32$ 位整数也返回 $-1$。

func nextGreaterElement(n int) int {
	s := []byte(strconv.Itoa(n))
	n = len(s)
	i, j := n-2, n-1
	for ; i >= 0 && s[i] >= s[i+1]; i-- {
	}
	if i < 0 {
		return -1
	}
	for ; j >= 0 && s[i] >= s[j]; j-- {
	}
	s[i], s[j] = s[j], s[i]
	for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
	ans, _ := strconv.Atoi(string(s))
	if ans > math.MaxInt32 {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源