同向双指针（上）

摘要

Two Sum的第十一种变形题 – 两数之差
全零子串问题
数组去重问题

同向双指针

两根指针都从头出发，朝着同一个方向移动

610 · 两数差等于目标值

求两数之差等于给定的 target，要求用O(1)空间复杂度完成
Two Sum 的第 11 个变形题

当不能使用哈希表时，可以在排序数据集上进行二分来替代，不能使用哈希表的情况比如数据集很大，或者题目要求不适用额外空间。

func TwoSum7(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}

	target = int(math.Abs(float64(target)))
	j := 1
	for i := 0; i < len(nums); i++ {
		j = max(j, i+1)
		// 找到第一个 nums[j]-nums[i] >= target 的 j
		for j < len(nums) && nums[j]-nums[i] < target {
			j++
		}
		if j >= len(nums) {
			break
		}
		if nums[j]-nums[i] == target {
			return []int{nums[i], nums[j]}
		}
	}
	return []int{-1, -1}
}

同向双指针的模板

func Template(n int) {
	j := 1
	for i := 0; i < n; i++ {
		for j < n && i,j的搭配不满足条件 {
			j++
		}
		if j >= n {
			break
		}
		处理i,j这次搭配
	}
}

时间复杂度

同向双指针时间复杂度 = O(n)
两根指针同向而行，都不会“回头”
每个指针访问数组中每个元素最多一次

1870 · 全零子串的数量

求出字符串中全0子串的个数
001000 有 5个0、3个00，1个000，共9个子串

/**
 * @param str: the string
 * @return: the number of substrings
 */
func StringCount(str string) int {
	if len(str) == 0 {
		return 0
	}
	j := 1
	ans := 0
	for i := 0; i < len(str); i++ {
		if str[i] != '0' {
			continue
		}
		j = max(i+1, j)
		for j < len(str) && str[j] == '0' {
			j++
		}
		ans += j - i
	}
	return ans
}

521 · 去除重复元素

套模板

func Deduplication(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	sort.Ints(nums)
	i, j := 0, 1
	for i = 0; i < len(nums); i++ {
		for j < len(nums) && nums[j] == nums[i] {
			j++
		}
		if j >= len(nums) {
			break
		}
		nums[i+1] = nums[j]
	}
	return i + 1
}

func Deduplication(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	sort.Ints(nums)
	i := 0
	for j := 1; j < len(nums); j++ {
		if nums[j] != nums[i] {
			i++
			nums[i] = nums[j]
		}
	}
	return i + 1
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。