灵神常见算法

• 392. 判断子序列

• 3132. 找出与数组相加的整数 II

392. 判断子序列

使用双指针

• i指针指向第一个字符串，j指针指向第二个字符串。
• i、j指向字符相同，i和j都向右移动一次。
• i、j指向字符不同，j向右移动一次。
• 执行完毕后，i指针指向到了第一个字符串的末尾，是子序列，否则不是。

func isSubsequence(s string, t string) bool {
	i, j := 0, 0
	for i < len(s) && j < len(t) {
		if s[i] == t[j] {
			i++
		}
		j++
	}

	return i == len(s)
}

3132. 找出与数组相加的整数 II

nums1	4	8	12	16	20
nums2			10	14	18

• 需要去除两个元素，
  • 将数组进行排序，需要x最小，去掉nums1中两个尽量小的数。
  • 遍历前3个nums1中的元素，前3个元素中最少有一个不被移除的数。
  • 从第3个开始倒着遍历，nums1[i] 越大答案越小，第一个满足的就是答案。
• 类似于子序列问题，判断nums2 是不是 {nums1[i] + diff} 的子序列,使用双指针

func minimumAddedInteger(nums1 []int, nums2 []int) int {
	// 先排序
	slices.Sort(nums1)
	slices.Sort(nums2)

	// 遍历前3个nums1中的元素，移除的两个数必定在前3个元素中
	// 倒着遍历，nums1[i] 越大答案越小，第一个满足的就是答案
	for i := 2; i >= 0; i-- {
		x := nums2[0] - nums1[i] // 差值

		// 类似于子序列问题，判断nums2 是不是 {nums1[i] + diff} 的子序列,使用双指针 
		j := 0
		for _, v := range nums1[i:] {
			if nums2[j]-v == x {
				j++
				if j == len(nums2) { // k指针到末尾，说明两个数组相等
					return x
				}
			}
		}
	}

	return nums2[0] - nums1[0]
}