代码随想录day7 | 454 四数相加|| 383 赎金信 15 三数之和 18 四数之和

454 四个数相加==0

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
	// 1. 用哈希表存储 nums1 和 nums2 两者之和的所有可能情况
	// 2. 遍历 nums3 和 nums4 两者之和的相反数，如果在哈希表中存在，则结果加上哈希表中的值
	// 3. 返回结果
	sum1 := make(map[int]int)
	for _, n1 := range nums1 {  // 将前两个数组之和存入map
		for _, n2 := range nums2 {
			sum1[n1+n2]++
		}
	}

	sum2 := make(map[int]int)
	for _, n3 := range nums3{
		for _, n4 := range nums4{
			sum2[n3+n4]++
		}
	}

	var res int
	for k1, v1 := range sum1{
		if v2, ok := sum2[-k1]; ok { // k1 + k2 == 0 ,即题设条件
			res += v1*v2  //  v1 个组合 * v2 个组合
		}
	}
	return res
}

时间n*n +n*n + 最坏n = n^2  空间 map存储两数之和的组合 n*n = n^2

383 赎金信（判断一个字符串是否完全包含另一个字符串）

func canConstruct(ransomNote string, magazine string) bool {
	// 思考 在一个集合里面寻找元素，优先考虑哈希表
	m := make(map[rune]int)
	for _, val := range magazine {
		m[val]++
	}

	for _, val2 := range ransomNote{
		if v, ok := m[val2]; ok && v>0 { // 如果每个字符都能在map中找到，那么最终true
			m[val2]-- // 改字符数量-1
			continue // 进入下一次循环
		}
		return false // 未进入商城条件判断，那么说明出现字符不在map，或者数量超过，那么返回false
	}
	return true
}
时间 m+n  空间n

15 三数之和

func threeSum(nums []int) [][]int {
	// hash算法太复杂，去重太麻烦，直接考虑双指针思路了
	var res [][]int
	nums = insert_sort(nums)
	fmt.Println(nums)
	for i := 0; i < len(nums) - 2; i++{ // 最终也要给left，right预留位置，所以最后要空出两个元素位置
		if nums[i] > 0 { // 如果排序后的首个元素>0 ,后面怎么加都会>0
			return res
		}

		if i > 0 && nums[i] == nums[i-1] { // 和之前遍历结果对比，如果相同，那么跳过本次循环
			continue
		}

		left , right := i + 1, len(nums) - 1
		sum := nums[i] + nums[left] + nums[right]
		for left < right { // ！！！此处为什么不能写  sum != 0 && left < right ，因为这样一次循环最多只找到一个结果，但是可能有多个结果
			if sum > 0 { // 大于0说明要缩小，所以right左移
				right--
			}else if sum < 0 {
				left++
			}else {
				res = append(res, []int{nums[i], nums[left], nums[right]})
				// 针对左右指针去重
				left++
				for left < right && nums[left] == nums[left-1]{
					left++
				}
				right--
				for left < right && nums[right] == nums[right+1]{
					right--
				}
			}
			sum = nums[i] + nums[left] + nums[right]
		}
	}
	return res
}
// 总结，难点在于思路，以及对三个指针的去重操作，涉及到去重，所以优先考虑的hash表算法复杂度太高放弃了，然后考虑双指针方法，通过先排序然后遍历一次，之后内部双指针向中间移动，实现三指针元素之和==0，之后就是针对指针去重，去重原理就是用当前指针和之前的指针对比，这样相当于新的结果集和老的结果集对比，实现对结果集的去重


// 时间 插排n^2 + 遍历n*左右指针移动和n = n^2   空间 二维数组n^2

18 四数之和

func fourSum(nums []int, target int) [][]int {
	// 思路 三数之和外层再套一个for循环
	var res [][]int
	nums = quick_sort(nums)
	fmt.Println(nums)
	for i := 0; i < len(nums) - 3; i++ {
		if nums[i] > target && nums[i] > 0 { // 防止出现【-2，-1，0，1】 target = -3这种错误剪枝
			return res
		}
		if i > 0 && nums[i] == nums[i-1] { // 已经计算过同样的结果集，跳过
			continue
		}

		// 三数之和
		for j := i+1; j < len(nums) - 2; j++{
			if nums[i] + nums[j] > target && nums[i] + nums[j] > 0 {  // 剪枝，和大于0，说明nums【j】肯定>0, 此时往右两个元素也>0, 无论元素target是正数还是负数，都不可能缩小了，所以无需继续循环
				break  // 剪枝跳出当前循环
			}
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}

			left, right := j+1, len(nums)-1
			for left < right{
				sum := nums[i] + nums[j] + nums[left] + nums[right]
				if sum > target{
					right--
				}else if sum < target {
					left++
				}else {
					res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
					left++
					for left < right && nums[left] == nums[left-1]{
						left++
					}
					right--
					for left < right && nums[right] == nums[right+1]{
						right--
					}
				}
			}
		}

	}
	return res

}

func quick_sort(nums []int) []int {
	// 快速排序思想： 选择一个值，然后遍历列表，实现左边列表小于值， 右边大于值， 然后再对左右子列表快排
	if len(nums) <= 1 { // 递归终止条件
		return nums
	}

	// 为什么不能包含povid，如果包含，那么就是pivot被塞入左边或者右边的一个数组中，此时进入递归后，
	// 因为pivod在数组最左侧位置，并且右边元素或者都小于或者都大于pivod，此时就会陷入无限递归，每次都不会缩小问题规模
	pivot := nums[0]
	var left, right  []int
	for _, val := range nums[1:] {
		if val < pivot {
			left = append(left, val)
		} else {
			right = append(right, val)
		}
	}

	return append(append(quick_sort(left), pivot), quick_sort(right)...)
}

// 思考，本题主要在于边界条件以及剪枝的处理，何时return 何时break

时间 n^3  空间 n^2