双向搜索

robot · robot · commit 89cd86525c00 · 2022-06-07T23:38:07.000+08:00
diff --git a/problems/805.split-array-with-same-average.md b/problems/805.split-array-with-same-average.md
@@ -34,14 +34,22 @@ A[i] 的数据范围为 [0, 10000].
 
 实际上分出的**两个列表 B 和 C 的均值都等于列表 A 的均值**，这是本题的入手点。以下是证明：
 
+令 B 的长度为 K，A 的长度为 N。 则有 sum(B)/K = sum(C)/(N-K)。
+
+进而：
+
 ```
 sum(B) * (N - K) = sum(C) * K
 sum(B) * N = (sum(B) + sum(C)) * K
 sum(B) / K = (sum(B) + sum(C)) / N
 sum(B) / K = sum(A) / N
 ```
 
-因此我们可以枚举所有的 A 的大小 i，相应地 B 的大小就是 n - i，其中 n 为数组 A 的大小。而由于**两个列表 B 和 C 的均值都等于列表 A 的均值**。因此可以提前计算出 A 的均值 avg，那么 A 的总和其实就是 i _ avg ，我们使用回溯找到一个和为 i _ avg 的组合，即可返回 true，否则返回 false。
+因此我们可以枚举所有的 A 的大小 i，相应地 B 的大小就是 n - i，其中 n 为数组 A 的大小。
+
+而由于**两个列表 B 和 C 的均值都等于列表 A 的均值**。因此可以提前计算出 A 的均值 avg，那么 A 的总和其实就是 i \* avg ，我们使用回溯找到一个和为 i \* avg 的组合，即可返回 true，否则返回 false。
+
+值得注意的是，我们只需要枚举 i 为 1 到 N//2 范围即可，这可以达到剪枝的效果。
 
 核心代码：
 
@@ -57,9 +65,9 @@ def splitArraySameAverage(self, A: List[int]) -> bool:
         return False
 ```
 
-上面代码由于回溯里面嵌套了 sum，因此时间复杂度为**回溯的时间复杂度 \* sum 的时间复杂度**，因此总的时间复杂度在最坏的情况下是 $n * 2^n$。
+上面代码由于回溯里面嵌套了 sum，因此时间复杂度为**回溯的时间复杂度 \* sum 的时间复杂度**，因此总的时间复杂度在最坏的情况下是 $n * 2^n$。代入题目的 n 范围是 30，一般这种复杂度只能解决 20 以下的题目，因此需要考虑优化。
 
-上面的代码思路上可行，但却有很多可以优化的地方。至少我们可以不用计算出来所有的组合之后再求和，而是直接计算**所有的和**的组合，这种算法的时间复杂度为 $2^n$。
+我们可以不计算出来所有的组合之后再求和，而是直接计算**所有的和**的组合，这种算法的时间复杂度为 $2^n$。
 
 核心代码：
 
@@ -75,17 +83,19 @@ def splitArraySameAverage(self, A: List[int]) -> bool:
         return False
 ```
 
-但是遗憾的是，这仍然不足以通过所有的测试用例。接下来，我们可以通过剪枝的手段来达到 AC 的目的。 很多**回溯**的题目都是基于剪枝来完成的。剪枝是回溯问题的核心考点。
+但是遗憾的是，这仍然不足以通过所有的测试用例。
+
+接下来，我们可以通过进一步剪枝的手段来达到 AC 的目的。 很多**回溯**的题目都是基于剪枝来完成的。剪枝是回溯问题的核心考点。
+
+这个技巧就是**双向搜索**，双向搜索相比之前的回溯可达到减少指数数字的效果，从 $O(2^n)$ 降低到 $O(2^(N//2))$。代入题目，这样指数变为了 30/2 = 15，就可以通过了。
 
-对于这道题来说，我们可以剪枝的点有两个：
+具体地，我们可以 combinationSum A 数组的一半（不妨称 A1），然后 combinationSum A 数组的令一半（不妨称 A2），那么 A1 和 A2 的总和如果是 avg \* i 不也行么？简单起见，我们可以令 A1 为数组 A 的前一半， A2 为数组的后一半。
 
-- 剪枝一：对于一个数组 [1,1,3]，任选其中两项，其组合有 3 种。分别是 (1,1), (1,3) 和 (1,3)。实际上，我们可以将两个 (1,3) 看成一样的（部分题目不能看成一样的，但本题可以），如果能将生成同样的组合剪枝掉就好了。我们可以排序的方式进行剪枝，具体参考 [40. 组合总和 II](https://github.com/azl397985856/leetcode/blob/master/problems/40.combination-sum-ii.md)
-- 剪枝二：由于每个数字都是整数，那么其和一定也是整数，因此如果和是小数，那么其一定不可能，可以剪枝。
+同时，为了避免这种加法，我们可以对问题进行一个转化。即将数组 A 的所有数都减去 avg，这样问题转化为找到一个和为 0 的组合，即可以找到一个和为 avg \* i 的组合。
 
 ## 关键点
 
-- 回溯解题模板
-- 两个剪枝
+- 双端搜索
 
 ## 代码
 
@@ -94,52 +104,43 @@ def splitArraySameAverage(self, A: List[int]) -> bool:
 Python3 Code:
 
 ```python
+class Solution(object):
+    def splitArraySameAverage(self, A):
+        from fractions import Fraction
+        N = len(A)
+        total = sum(A)
+        A = [a - Fraction(total, N) for a in A] # 转化后的 A，免于计算 sum
+
+        if N == 1: return False
+
+        S1 = {A[0]} # 所有 A1 可能的和的集合
+        for i in range(1, N//2):
+            # {a + A[i] for a in S1} 在之前选择的基础上选择 A[i] 的新集合
+            # {A[i]} 是仅选择 A[i] 的新集合
+            # S1 是不选择 A[i] 的集合
+            # | 是集合并操作
+            S1 = {a + A[i] for a in S1} | S1 | {A[i]}
+        if 0 in S1: return True
+
+        S2 = {A[-1]} # 所有 A2 可能的和的集合
+        for i in range(N//2, N-1):
+            S2 = {a + A[i] for a in S2} | S2 | {A[i]}
+        if 0 in S2: return True
+        # 为了避免 B 选择了所有的 A，这样 C 就是空了，我们增加一个这样的判断
+        sleft = sum(A[i] for i in range(N//2))
+        sright = sum(A[i] for i in range(N//2, N))
+
+        return any(-ha in S2 and (ha, -ha) != (sleft, sright) for ha in S1)
 
-class Solution:
-    def combinationSum(self, candidates: List[int], count: int) -> List[List[int]]:
-        size = len(candidates)
-        if size == 0:
-            return []
- 
-        # 还是先排序，主要是方便去重
-        candidates.sort()
- 
-        ans = []
-        self._find_path(candidates, ans, 0, count, 0, size)
-        return ans
- 
-    def _find_path(self, candidates, ans, path_sum, count, begin, size):
-        if count == 0:
-            ans.append(path_sum)
-            return
-        else:
-            for i in range(begin, size):
-                # 剪枝一。 注意这里的 i > begin 这个条件
-                if i > begin and candidates[i] == candidates[i - 1]:
-                    continue
-                self._find_path(candidates, ans, path_sum + candidates[i], count - 1, i + 1, size)
- 
-    def splitArraySameAverage(self, A: List[int]) -> bool:
-        n = len(A)
-        avg = sum(A) / n
- 
-        for i in range(1, n // 2 + 1):
-            # 剪枝二
-            if abs(i * avg - int(i * avg)) > 1e-6:
-                continue
-            for s in self.combinationSum(A, i):
-                if abs(s - avg * i) < 1e-6:
-                    return True
-        return False
 
 ```
 
 **复杂度分析**
 
 令 n 为数组长度。
 
-- 时间复杂度：$O(2^n)$
-- 空间复杂度：$O(n)$
+- 时间复杂度：$O(2^(N//2))$
+- 空间复杂度：$O(2^(N//2))$
 
 > 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
 
