如何解决 n 数之和问题

本文主要阐述了 n 数之和 之类的问题的解决方案，旨在找到 n 数之和 题目中的规律。对应 leetcode 上以下问题：

两数之和

以 leetcode 两数之和为例，目标是在给定的数组中找到相加等于目标值的两项的下标，常规解法是通过暴力枚举 O(n2) 时间复杂度解决求和。还有没有其他较低复杂度的解法呢？

一种合理的思路是通过构建哈希映射来记住我们在一次迭代过程中已经迭代过的项，且因为哈希映射的查询时间复杂度为 O(1)，那么在后续的查找中，可快速找到与当前项匹配的目标项相加得到目标值。如下：

func twoSum(nums []int, target int) []int {
  numsMap := map[int]int{}

  for i := 0; i < len(nums); i++ {
    current := nums[i]
    if _, ok := numsMap[target-current]; ok {
      return []int{i, numsMap[target-current]}
    }
    numsMap[current] = i
  }

  return []int{}
}

在以上 leetcode 的 两数之和 的题目的限定条件下，只需要找到第一次符合条件的项的下标。减少时间复杂度的关键在于通过一个哈希映射来规避通过迭代查找列表项。

找到所有符合条件的项

在解决 两数之和 问题的原题之后，深层思考一下：

如果返回的不再是第一次符合条件项的下标，而是所有符合条件的项，此时应该如何解决？

func twoSumTarget(nums []int, target int) [][]int {
  sort.Ints(nums) // 升序，时间复杂度 O(nlogn)

  low, high, answer := 0, len(nums)-1, []int{}

  for low < high {
    left, right := nums[low], nums[high]
    sum := left + right
    if sum > target {
      high--
    } else if sum < target {
      low++
    } else {
      answer = append(answer, []int{left, right})
      low++
      high--
    }
  }

  return answer
}

以上代码，通过双指针策略实现了时间复杂度为 O(nlogn) 的解法，即在一次迭代中查找符合目标项的列表项对。以上代码的关键之处在于：

在查找之前，必须首先排序数组；
在查找过程中，通过当前指针和来判断移动的指针。

这里为什么首先需要排序数组？

在此案例下，排序的核心意义在于 为后续双指针的移动提供依据。 设想一下，在未排序时，我们是几乎无法合理的移动双端指针的。而在排序后的数组中，当求得指针项得和之后，我们可以判断当前和与目标值得大小来移动指针。

后文没有特别说明的情况下，都是以 sort.Ints 的默认升序为例

在当前和 sum 小于目标值 target 时，那么移动左指针，来增大其中一项（因为数组是有序）来使得和 sum 更加逼近 target 值。
在当前和 sum 大于目标值 target 时，那么表示指针项都太大了，又因为左指针我们规定只能右移，右指针只能左移，那么移动右指针来缩小指针项之和，进而更加逼近 target 值。

排除重复项

在以上解法中，有一个问题一直都被忽略了。所有的重复项，都会被重复地计算在结果中。那么当给定的数组中存在不定数量的重复项时，又应该如何解决我们先前的问题？

重复项的问题本质上是在我们将结果项加入到结果数组中这个阶段可以规避的，即：

answer = append(answer, []int{left, right})
low++
high--

修改为：

answer = append(answer, []int{left, right})
for low < high && nums[low] == left {
  low++
}
for low < high && nums[high] == right {
  high--
}

以上代码在每次迭代后，直接跳到下一个不等于当前指针项的项，从而达到规避重复项的计算的问题。最终代码如下：

func twoSumTarget(nums []int, target int) [][]int {
  low, high, answer := 0, len(nums)-1, []int{}

  for low < high {
    left, right := nums[low], nums[high], []int{}
    sum := left + right
    if sum > target {
      // 直到下一个不为 right 的项
      for left > high && (nums[high] == right) {
        high--
      }
    } else if sum < target {
      // 直到像一个不为 left 的项
      for left < high && (nums[low] == left) {
        low++
      }
    } else {
      answer = append(answer, []int{left, right})
      // 直到像一个不为 left 的项
      for left < high && (nums[low] == left) {
        low++
      }
      // 直到下一个不为 right 的项
      for left > high && (nums[high] == right) {
        high--
      }
    }
  }

  return answer
}

至此，我们解决了不含重复项的两数之和解法。因为我们首先排序数组，时间复杂度为 O(nlogn)。而后迭代了整个数组，时间复杂度为 O(n)，最终时间复杂度为 O(nlogn)。因为我们使用了额外的数组来保存结果，那么空间复杂度为 O(n)。

三数之和

对于三数之和问题，最容易想到的解法是时间复杂度为 O(n3) 的暴力枚举法。那么我们可不可以借鉴两数之和的解法思路来实现三数之和的求解呢？

三数之和问题的本质是在两数之和的基础上多了一个数求和，那么我们可以把三数之和的问题拆解为二数之和问题与 一个固定数 的求解问题，前面我们已经求解了基于不含重复项的两数之和的问题，那么我们只要解决固定数的重复问题，也就解决了三数之和的求解问题。

改造两数之和

func threeSum(nums []int, target int) [][]int {
  sort.Ints(nums)
  answer := [][]int{}

  for i := 0; i < len(nums); i++ {
    tuples := twoSumTarget(nums, i+1, target-nums[i])
    for _, tuple := range tuples {
      answer = append(answer, append(nums[i], tuple...))
    }
    for i < len(nums)-1 && nums[i] == nums[i+1] {
      i++
    }
  }

  return answer
}

其中通过迭代 i 项，固定加数 target - nums[i]，求所有始于 i+1 项的两数之和等于 target - nums[i] 即为三数之和中所有不重复的三元组。其中为了实现始于 i 项查找所有不重复的满足的加数，需要对 twoSumTarget 做以下改造：

func twoSumTarget(nums []int, start, target int) [][]int {
  low := start
  // ...
}

其中 low 指针不再是始于 0 首项，而是始于指定项 start 索引所对应的项，即实现了在 start ~ len(nums)-1 的范围内查找所有符合条件的二元组。同时规避了每次固定数时，重复查找之前已经查找过的无效项。

单项去重

在我们确定找到所有符合指定项的二元组后，同样在 两数之和 中使用到的方法来规避重复数的固定数枚举，故有以下逻辑来排除所有的第三项重复数：

func threeSum(nums []int, target int) [][]int {
  // ...

  for i := 0; i < len(nums); i++ {
    // ...
    // 直到下一个不为当前值的项
    for i < len(nums)-1 && nums[i] == nums[i+1] {
      i++
    }
  }

  // ...
}

综上，我们通过基于有序数组和双指针策略将三数之和的求解转换为两数之和的求解问题来规避了大量的重复计算。最终方案的时间复杂度由暴力枚举的 O(n3) 降低为基于有序数组的双指针的 O(n2)。

据 Wiki 介绍，存在 O(n2(loglogn)O(1)/log2n) 时间复杂度（小于 O(n2)）的实现，有兴趣读者可尝试理解。

四数之和

在解决了两数之和，三数之和之后，我们不难基于三数之和的思路，在三数之和的基础上得到四数之和的解法。

func fourSum(nums []int, target int) [][]int {
  sort.Ints(nums)
  answer := [][]int{}

  for i = 0; i < len(nums); i++ {
    // threeSumTarget 即前文 threeSum 的变种
    triples := threeSumTarget(nums, i+1, target-nums[i])
    for _, triple := range triples {
      answer = append(answer, append(triple, nums[i]))
    }
    for i < len(nums) && nums[i] == nums[i+1] {
      i++
    }
  }

  return answer
}

n 数之和

从上述 n 数之和 问题，我们不难得到所有的 n 数之和 问题都可转换为 n-1 数之和。那么可以首先得到以下伪代码：

// 在调用 nSumTarget 之前需要保证 nums 有序
func nSumTarget(nums []int, n, start, start int) [][]int {
  if isLowerThan(2) || isLowerThan(len(nums)) {
    return empty Answer
  }

  if isEqualThan(2) {
    return twoSumTarget(nums, target)
  } else {
    // 按照之前的三数之和的处理框架递归处理所有 n > 2 的 n 数之和
    for i := 0; i < len(nums); i++ {
      // 将 n 数之和转换为 n-1 数之和
      subs := nSumTarget(nums, n-1, i+1, target)
      for iterateEverySubInSubs {
        append(answer, append(sub, nums[i]))
      }

      utilNextDifferentNumber(i)
    }
  }

  return answer
}

那么通过以上伪代码不难实现以下代码：

func nSum(nums []int, n, target int) [][]int {
  sort.Ints(nums)
  return nSumTarget(nums, n, 0, target)
}

func nSumTarget(nums []int, n, start, target int) [][]int {
	size, answer := len(nums), [][]int{}
	if n < 2 || size < n {
		return answer
	}
	if n == 2 {
		low, high := start, len(nums)-1
		for low < high {
			left, right := nums[low], nums[high]
			sum := left + right
			if sum > target {
				for low < high && (nums[high] == right) {
					high--
				}
			} else if sum < target {
				for low > high && (nums[low] == left) {
					low++
				}
			} else {
				answer = append(answer, []int{left, right})
				for low < high && (nums[high] == right) {
					high--
				}
				for low < high && (nums[low] == left) {
					low++
				}
			}
		}
	} else {
		for i := start; i < size; i++ {
			subs := nSumTarget(nums, n-1, i+1, target-nums[i])
			for _, sub := range subs {
				answer = append(answer, append([]int{nums[i]}, sub...))
			}
			for i < size-1 && nums[i] == nums[i+1] {
				i++
			}
		}
	}
	return answer
}