1. 接雨水

给出n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

示例1：

  1. 输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
  2. 输出：6

解释：
image.png

  • 上面由数组表示柱子的高度图，在这种情况下，可以接6个单位的雨水（蓝色部分表示雨水）

示例2：

  1. 输入：height = [4, 2, 0, 3, 2, 5]
  2. 输出：9

1.1 递归解法

首先，我们将高度为0的柱子，也视为有柱子，只是它的高度很矮。这样一来，雨水只会存储在当前柱子的上方

柱子上可以存水，需要满足以下几个条件：

  • 【条件一】当前柱子的左侧和右侧，必须有柱子。也就是说第一根柱子和最后一根柱子的上方，一定不会存水

  • 【条件二】当前柱子的左侧最高柱子与右侧最高柱子，任意一侧的高度，都必须大于当前柱子的高度。否则，当前柱子上一定不会存水

可以存水的情况：

  • 当前柱子不能是第一根或最后一根，即：size - 1 > index > 0

  • 当前柱子的左侧最高柱子与右侧最高柱子，较矮一侧的高度 > 当前柱子的高度。此时它们的高度差值，即为当前柱子上的存水量

    • 存水量 = min(左侧最高柱子的高度, 右侧最高柱子的高度) - 前柱子的高度

代码实现：

  1. class Solution {
  3.     // 表示柱子高度的数组
  4.     fileprivate var _arr : [Int];
  6.     init(arr : [Int]) {
  7.         _arr = arr;
  8.     }
  10.     func trap() -> Int {
  12.         if(_arr.count < 3){
  13.             // 小于3根柱子，无法存水
  14.             return 0;
  15.         }
  17.         var sum = 0;
  19.         for i in 1..<(_arr.count - 1) {
  21.             // 获取当前柱子高度
  22.             let currHeight = _arr[i];
  23.             // 获取左侧最高柱子的高度
  24.             let leftMaxHeight = getLeftMaxHeight(index: i - 1);
  25.             // 获取右侧最高柱子的高度
  26.             let rightMaxHeight = getRightMaxHeight(index: i + 1);
  28.             // 获取左右较矮一侧柱子的高度
  29.             let minMaxHeight = min(leftMaxHeight, rightMaxHeight);
  31.             // 如果较矮一侧柱子的高度 <= 当前柱子高度
  32.             if(minMaxHeight <= currHeight){
  33.                 // 无法存水，跳过循环
  34.                 continue;
  35.             }
  37.             // 否则，当前柱子上的存水量 = 较矮一侧柱子的高度 - 当前柱子高度
  38.             // 将其累加到总存水量中
  39.             sum += (minMaxHeight - currHeight);
  40.         }
  42.         // 返回所有柱子上的总存水量
  43.         return sum;
  44.     }
  46.     // 获取左侧最高柱子的高度
  47.     fileprivate func getLeftMaxHeight(index : Int) -> Int {
  49.         if(index < 1){
  50.             return _arr[index];
  51.         }
  53.         let curr = _arr[index];
  54.         let left = getLeftMaxHeight(index: index - 1);
  56.         return max(curr, left);
  57.     }
  59.     // 获取右侧最高柱子的高度
  60.     fileprivate func getRightMaxHeight(index : Int) -> Int {
  62.         if(index >= _arr.count - 1){
  63.             return _arr[_arr.count - 1];
  64.         }
  66.         let curr = _arr[index];
  67.         let right = getRightMaxHeight(index: index + 1);
  69.         return max(curr, right);
  70.     }
  71. }

1.2 缓存优化

定义两个数组，将当前柱子的左侧最高柱子的高度，以及右侧最高柱子的高度分别缓存

  1. class Solution {
  3.     // 表示柱子高度的数组
  4.     fileprivate var _arr : [Int];
  6.     init(arr : [Int]) {
  7.         _arr = arr;
  8.     }
  10.     fileprivate var _leftCache : [Int]?;
  11.     fileprivate var _rightCache : [Int]?;
  13.     func trap() -> Int {
  15.         if(_arr.count < 3){
  16.             // 小于3根柱子，无法存水
  17.             return 0;
  18.         }
  20.         // 初始化左侧缓存
  21.         _leftCache = [Int].init(repeating: -1, count: _arr.count);
  22.         // 初始化右侧缓存
  23.         _rightCache = [Int].init(repeating: -1, count: _arr.count);
  25.         var sum = 0;
  27.         for i in 1..<(_arr.count - 1) {
  29.             // 获取当前柱子高度
  30.             let currHeight = _arr[i];
  31.             // 获取左侧最高柱子的高度
  32.             let leftMaxHeight = getLeftMaxHeight(index: i - 1);
  33.             // 获取右侧最高柱子的高度
  34.             let rightMaxHeight = getRightMaxHeight(index: i + 1);
  36.             // 获取左右较矮一侧柱子的高度
  37.             let minMaxHeight = min(leftMaxHeight, rightMaxHeight);
  39.             // 如果较矮一侧柱子的高度 <= 当前柱子高度
  40.             if(minMaxHeight <= currHeight){
  41.                 // 无法存水，跳过循环
  42.                 continue;
  43.             }
  45.             // 否则，当前柱子上的存水量 = 较矮一侧柱子的高度 - 当前柱子高度
  46.             // 将其累加到总存水量中
  47.             sum += (minMaxHeight - currHeight);
  48.         }
  50.         // 返回所有柱子上的总存水量
  51.         return sum;
  52.     }
  54.     // 获取左侧最高柱子的高度
  55.     fileprivate func getLeftMaxHeight(index : Int) -> Int {
  57.         if(_leftCache![index] != -1){
  58.             // 命中缓存
  59.             return _leftCache![index];
  60.         }
  62.         // 计算并写入缓存
  63.         if(index < 1) {
  64.             _leftCache![index] = _arr[index];
  65.         }
  66.         else {
  67.             let curr = _arr[index];
  68.             let left = getLeftMaxHeight(index: index - 1);
  69.             _leftCache![index] = max(curr, left);
  70.         }
  72.         return _leftCache![index];
  73.     }
  75.     // 获取右侧最高柱子的高度
  76.     fileprivate func getRightMaxHeight(index : Int) -> Int {
  78.         if(_rightCache![index] != -1) {
  79.             // 命中缓存
  80.             return _rightCache![index];
  81.         }
  83.         // 计算并写入缓存
  84.         if(index >= _arr.count - 1) {
  85.             _rightCache![index] = _arr[_arr.count - 1];
  86.         }
  87.         else {
  88.             let curr = _arr[index];
  89.             let right = getRightMaxHeight(index: index + 1);
  90.             _rightCache![index] = max(curr, right);
  91.         }
  93.         return _rightCache![index];
  94.     }
  95. }

1.3 递推解法

计算存水量时，我们会从左往右遍历每一根柱子，所以左侧最高柱子的高度，可以跟随遍历一起计算

但右侧最高柱子的高度，如果在计算存水量时通过子循环遍历结果，会产生大量重复子问题的计算，影响效率。所以我们最好提前将计算出每一根柱子的右侧最高柱子的高度，并将其写入缓存

  1. class Solution {
  3.     // 表示柱子高度的数组
  4.     fileprivate var _arr : [Int];
  6.     init(arr : [Int]) {
  7.         _arr = arr;
  8.     }
  10.     // 获取右侧柱子的缓存
  11.     fileprivate func getRightCache() -> [Int] {
  13.         // 初始化右侧柱子的缓存
  14.         var rightCache = [Int].init(repeating: 0, count: _arr.count);
  15.         // 初始化右侧最高柱子的高度
  16.         var rightMax = 0;
  18.         for j in (1..<(_arr.count - 1)).reversed() {
  19.             // 获取后一根柱子的高度
  20.             let next = _arr[j + 1];
  21.             // 如果后一根柱子的高度 > 右侧最高柱子的高度
  22.             if(next > rightMax){
  23.                 // 更新右侧最高柱子的高度
  24.                 rightMax = next;
  25.             }
  26.             // 写入缓存
  27.             rightCache[j] = rightMax;
  28.         }
  30.         return rightCache;
  31.     }
  33.     func trap() -> Int {
  35.         if(_arr.count < 3){
  36.             // 小于3根柱子，无法存水
  37.             return 0;
  38.         }
  40.         // 获取右侧柱子的缓存
  41.         let rightCache = getRightCache();
  42.         // 初始化左侧最高柱子的高度
  43.         var leftMaxHeight = 0;
  44.         // 初始化总存水量
  45.         var sum = 0;
  47.         for i in 1..<(_arr.count - 1) {
  49.             // 获取当前柱子高度
  50.             let currHeight = _arr[i];
  52.             // 获取前一根柱子的高度
  53.             let prev = _arr[i - 1];
  54.             // 如果前一根柱子的高度 > 左侧最高柱子的高度
  55.             if(prev > leftMaxHeight){
  56.                 // 更新左侧最高柱子的高度
  57.                 leftMaxHeight = prev;
  58.             }
  60.             // 从缓存中获取右侧最高柱子的高度
  61.             let rightMaxHeight = rightCache[i];
  62.             // 获取左右较矮一侧柱子的高度
  63.             let minMaxHeight = min(leftMaxHeight, rightMaxHeight);
  65.             // 如果较矮一侧柱子的高度 <= 当前柱子高度
  66.             if(minMaxHeight <= currHeight){
  67.                 // 无法存水，跳过循环
  68.                 continue;
  69.             }
  71.             // 否则，当前柱子上的存水量 = 较矮一侧柱子的高度 - 当前柱子高度
  72.             // 将其累加到总存水量中
  73.             sum += (minMaxHeight - currHeight);
  74.         }
  76.         // 返回所有柱子上的总存水量
  77.         return sum;
  78.     }
  79. }

1.4 单调栈

单调栈：单调递增或单调减的栈，跟单调队列差不多，但是只用到它的一端

使用单调递增栈，根据柱子的高度进行对比，存储柱子的索引值。栈顶元素arr[top]作为当前柱子，栈顶元素的下一个元素arr[left]作为左侧柱子，arr[i]作为右侧柱子

当前栈非空，并且当前柱子的高度 < 右侧柱子的高度，进入栈的遍历

获取当前柱子，并将其出栈。再获取左侧柱子，如果不存在左侧柱子，结束栈的遍历

存在，先使用i - left - 1计算存水区域，再使用min(left, right) - curr计算存水量。通过存水量 * 存水区域获得区域内柱子的存水量，将其加入到总存水量中

代码实现：

  1. class Solution {
  3.     // 表示柱子高度的数组
  4.     fileprivate var _arr : [Int];
  6.     init(arr : [Int]) {
  7.         _arr = arr;
  8.     }
  10.     func trap() -> Int {
  12.         if(_arr.count < 3){
  13.             // 小于3根柱子，无法存水
  14.             return 0;
  15.         }
  17.         // 初始化总存水量
  18.         var sum = 0;
  19.         // 初始化栈结构
  20.         let stack = LinkedStack<Int>();
  22.         // 遍历所有柱子
  23.         for i in 0..<_arr.count {
  25.             // 获取当前柱子的高度，作为右侧柱子的高度使用
  26.             let right = _arr[i];
  28.             // 非空栈 && 当前柱子的高度 < 右侧柱子的高度，进入栈的遍历
  29.             while(!stack.isEmpty() && _arr[stack.getTop()!] < right){
  31.                 // 栈顶元素出栈，作为当前柱子的索引值
  32.                 let currIndex = stack.pop()!;
  33.                 // 获得当前柱子的高度
  34.                 let curr = _arr[currIndex];
  36.                 // 再次获取栈顶元素，作为左侧柱子的索引值
  37.                 let leftIndex = stack.getTop();
  39.                 // 判断是否存在左侧柱子
  40.                 if(leftIndex == nil){
  41.                     // 不存在，结束栈的遍历
  42.                     break;
  43.                 }
  45.                 // 存水区域 = 当前索引值 - 左侧柱子的索引值 - 1
  46.                 let width = i - leftIndex! - 1;
  47.                 // 获得左侧柱子的高度
  48.                 let left = arr[leftIndex!];
  49.                 // 当前柱子上的存水量 = 较矮一侧柱子的高度 - 当前柱子高度
  50.                 let difference = min(left, right) - curr;
  51.                 // 总存水量 = 当前柱子上的存水量 * 可存水的柱子总数
  52.                 // 将其累加到总存水量中
  53.                 sum += difference * width;
  54.             }
  56.             // 将右侧柱子的索引值入栈，进入下一次栈的遍历，作为当前柱子的索引值使用
  57.             stack.push(element: i);
  58.         }
  60.         // 返回所有柱子上的总存水量
  61.         return sum;
  62.     }
  63. }

  • 时间复杂度：O(n)，因为从0到n-1的每个索引值最多只会入栈和出栈各一次

  • 空间复杂度：O(n)，它主要取决于栈空间，栈的大小不会超过n

1.5 双指针

使用双指针leftIndex和rightIndex，分别表示左右两侧柱子的索引值。leftIndex默认为0，只能向右移动。rightIndex默认为n - 1，只能向左移动

使用leftMaxHeight和rightMaxHeight，分别记录左右两侧最高柱子的高度。leftMaxHeight默认为第一根柱子的高度，rightMaxHeight默认为最后一根柱子的高度

只要左右指针不相遇，就会持续遍历，内部逻辑如下：

  • 如果当前左侧柱子的高度 < 当前右侧柱子的高度，必然leftMaxHeight < rightMaxHeight，通过左侧最高柱子的高度 - 当前左侧柱子的高度得到存水量。将左指针向右移动，并更新leftMaxHeight

  • 如果当前左侧柱子的高度 >= 当前右侧柱子的高度，必然leftMaxHeight >= rightMaxHeight，通过右侧最高柱子的高度 - 当前右侧柱子的高度得到存水量。将右指针向左移动，并更新rightMaxHeight

解读：左指针右移的终止条件是找到>= rightMaxHeight的leftMaxHeight，也就是说一旦左指针终止右移，此时的arr[leftIndex]一定是leftMaxHeight，并且>= rightMaxHeight。同理，右指针左移的终止条件是找到> leftMaxHeight的rightMaxHeight，而此时的arr[rightIndex]就是rightMaxHeight

代码实现：

  1. class Solution {
  3.     // 表示柱子高度的数组
  4.     fileprivate var _arr : [Int];
  6.     init(arr : [Int]) {
  7.         _arr = arr;
  8.     }
  10.     func trap() -> Int {
  12.         if(_arr.count < 3){
  13.             // 小于3根柱子，无法存水
  14.             return 0;
  15.         }
  17.         // 初始化总存水量
  18.         var sum = 0;
  20.         // 左侧柱子的索引值，默认为第一根
  21.         var leftIndex = 0;
  22.         // 左侧最高柱子的高度，默认为第一根柱子的高度
  23.         var leftMaxHeight = _arr[leftIndex];
  25.         // 右侧柱子的索引值，默认为最后一根
  26.         var rightIndex = _arr.count - 1;
  27.         // 右侧最高柱子的高度，默认为最后一根柱子的高度
  28.         var rightMaxHeight = _arr[rightIndex];
  30.         // 只要左右指针不相遇，就会持续遍历
  31.         while(leftIndex != rightIndex){
  33.             // 获得左侧柱子的高度
  34.             var leftHeight = _arr[leftIndex];
  35.             // 获得右侧柱子的高度
  36.             var rightHeight = _arr[rightIndex];
  38.             // 如果左侧比右侧柱子的高度矮，必然左侧最高比右侧最高矮
  39.             // 如果不好理解，也可以改成leftMaxHeight < rightMaxHeight
  40.             // 两种写法目的相同，都是为了找到更矮一侧的柱子，计算它的存水量
  41.             // 如果找不到>=rightMaxHeight的leftMaxHeight，则移动的永远都是左指针
  42.             if(leftHeight < rightHeight){
  44.                 // 存水量取决于左右最高柱子中较矮一侧的高度，与当前柱子高度的差值
  45.                 // 因为：左侧高度 < 右侧高度，所以：左侧最高柱子的高度 < 右侧最高柱子的高度
  46.                 // 故此，我们不必求解min(leftMaxHeight, rightMaxHeight)，直接使用以下公式即可
  47.                 // 存水量 = 左侧最高柱子的高度 - 当前左侧柱子的高度
  48.                 sum += leftMaxHeight - leftHeight;
  49.                 // 左侧柱子的索引值+1
  50.                 leftIndex += 1;
  51.                 // 获得当前左侧柱子的高度
  52.                 leftHeight = _arr[leftIndex];
  53.                 // 更新左侧最高
  54.                 leftMaxHeight = max(leftHeight, leftMaxHeight);
  55.             }
  56.             else{
  58.                 // 同理：左侧高度 >= 右侧高度，所以：左侧最高柱子的高度 >= 右侧最高柱子的高度
  59.                 // 故此，存水量 = 右侧最高柱子的高度 - 当前右侧柱子的高度
  60.                 sum += rightMaxHeight - rightHeight;
  61.                 // 左侧柱子的索引值-1
  62.                 rightIndex -= 1;
  63.                 // 获得当前右侧柱子的高度
  64.                 rightHeight = _arr[rightIndex];
  65.                 // 更新右侧最高
  66.                 rightMaxHeight = max(rightHeight, rightMaxHeight);
  67.             }
  68.         }
  70.         // 返回所有柱子上的总存水量
  71.         return sum;
  72.     }
  73. }

  • 时间复杂度：O(n)，两个指针的移动总次数不超过n

  • 空间复杂度：O(1)，只需要使用常数的额外空间

2. 分割等和子集

给出一个只包含正整数的非空数组nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等

示例1：

  1. 输入：nums = [1, 5, 11, 5]
  2. 输出：true
  • 数组可以分割成[1, 5, 5]和[11]

示例2：

  1. 输入：nums = [1, 2, 3, 5]
  2. 输出：false
  • 数组不能分割成两个元素和相等的子集

2.1 递归解法

问题可以归结为：假设S表示所有给定数字的总和，则两个相等的⼦集的和必须等于S / 2

⼦问题：找到总和为S / 2的⼦集

状态：数字只能使用⼀次，要么属于S / 2，要么不属于S / 2

如果给出的集合具有以下特征，则一定无法分割出等和的子集

  • 集合中元素小于2个

  • 集合中元素之和为奇数

  • 集合中最大元素 > 元素之和的一半

否则，我们传入目标数（元素之和的一半），尝试用它减去符合条件的元素。如果可以遍历出一种方式，最终可将目标数减为0，则表示集合可分割出等和的子集

集合中元素只有两种可能性：

  • 当前元素 > 剩余目标数，则不可能放入当前子集中

  • 当前元素 < 剩余目标数，则有可能放入当前子集中

    • 放入当前子集中的前提，必须满足：目标数 - 其他元素 - 当前元素 = 0

代码实现：

  1. class Solution {
  3.     fileprivate var _arr : [Int];
  5.     init(arr : [Int]) {
  6.         _arr = arr;
  7.     }
  9.     // 集合元素总和的一半，作为目标值
  10.     fileprivate var _target : Int = 0;
  12.     func canPartition() -> Bool {
  14.         // 集合中元素个数小于2个
  15.         if(_arr.count < 2){
  16.             // 不可能分割
  17.             return false;
  18.         }
  20.         // 元素总和
  21.         var sum = 0;
  22.         // 最大元素
  23.         var maxItem = 0;
  24.         // 遍历集合中所有元素
  25.         for i in _arr {
  26.             // 累加总和
  27.             sum += i;
  28.             // 计算出最大元素
  29.             maxItem = max(i, maxItem);
  30.         }
  32.         // 判断总和为奇数
  33.         if(sum % 2 == 1) {
  34.             // 奇数，不可能分割出相等的子集
  35.             return false;
  36.         }
  38.         // 目标的结果数，即：总和取半
  39.         let target = sum / 2;
  41.         // 判断最大元素是否超过目标数
  42.         if(maxItem > target){
  43.             // 超过，不可能分割出相等的子集
  44.             return false;
  45.         }
  47.         // 是否可分割出等和的子集
  48.         let reslut = getResult(index: 0, target: target);
  49.         // 返回结果
  50.         return reslut;
  51.     }
  53.     // 是否可分割出等和的子集
  54.     func getResult(index : Int, target : Int) -> Bool {
  56.         // 索引超出集合，表示所有元素都尝试过，无法分割出相等的子集
  57.         if(index >= _arr.count){
  58.             return false;
  59.         }
  61.         // 目标数减到0，可以分割出相等的子集
  62.         if(target == 0){
  63.             return true;
  64.         }
  66.         // 判断当前元素是否超过剩余的目标数
  67.         if(_arr[index] > target){
  68.             // 超过，跳过该元素，继续后面的元素
  69.             return getResult(index: index + 1, target: target);
  70.         }
  72.         // 否则，尝试选择该元素，剩余目标数 = 当前目标数 - 当前元素
  73.         let residue = target - _arr[index];
  74.         // 继续后面的元素，并传入剩余目标数，表示选择该元素
  75.         let reslut = getResult(index: index + 1, target: residue);
  76.         // 判断选择该元素之后的结果
  77.         if(!reslut){
  78.             // 无法分割出相等的子集，证明该元素不符合加入子集的条件。跳过该元素，继续后面的元素
  79.             return getResult(index: index + 1, target: target);
  80.         }
  82.         // 分割出相等的子集，直接返回
  83.         return reslut;
  84.     }
  85. }

2.2 缓存优化

定义二维数组，空间开辟大小为：(集合大小 +1) * (目标数 + 1)

  1. class Solution {
  3.     fileprivate var _arr : [Int];
  5.     init(arr : [Int]) {
  6.         _arr = arr;
  7.     }
  9.     // 集合元素总和的一半，作为目标值
  10.     fileprivate var _target : Int = 0;
  11.     // 缓存
  12.     fileprivate var _cache : [[Int]]?;
  14.     func canPartition() -> Bool {
  16.         // 集合中元素个数小于2个
  17.         if(_arr.count < 2){
  18.             // 不可能分割出相等的子集
  19.             return false;
  20.         }
  22.         // 元素总和
  23.         var sum = 0;
  24.         // 最大元素
  25.         var maxItem = 0;
  26.         // 遍历集合中所有元素
  27.         for i in _arr {
  28.             // 累加总和
  29.             sum += i;
  30.             // 计算出最大元素
  31.             maxItem = max(i, maxItem);
  32.         }
  34.         // 判断总和为奇数
  35.         if(sum % 2 == 1) {
  36.             // 奇数，不可能分割出相等的子集
  37.             return false;
  38.         }
  40.         // 目标的结果数，即：总和取半
  41.         let target = sum / 2;
  43.         // 判断最大元素是否超过目标数
  44.         if(maxItem > target){
  45.             // 超过，不可能分割出相等的子集
  46.             return false;
  47.         }
  49.         // 初始化缓存大小
  50.         _cache = [[Int]](repeating: [Int](repeating: -1, count: target + 1), count: _arr.count + 1);
  52.         // 是否可分割出等和的子集
  53.         let reslut = getResult(index: 0, target: target);
  54.         // 返回结果
  55.         return reslut == 1;
  56.     }
  58.     // 是否可分割出等和的子集
  59.     func getResult(index : Int, target : Int) -> Int {
  61.         if(_cache![index][target] == -1){
  63.             // 索引超出集合，表示所有元素都尝试过，无法分割出相等的子集
  64.             if(index >= _arr.count){
  65.                 // 将结果写入缓存
  66.                 _cache![index][target] = 0;
  67.                 // 返回结果
  68.                 return _cache![index][target];
  69.             }
  71.             // 目标数减到0，可以分割出相等的子集
  72.             if(target == 0){
  73.                 // 将结果写入缓存
  74.                 _cache![index][target] = 1;
  75.                 // 返回结果
  76.                 return _cache![index][target];
  77.             }
  79.             // 判断当前元素是否超过剩余的目标数
  80.             if(_arr[index] > target){
  81.                 // 超过，跳过该元素，继续后面的元素
  82.                 // 将结果写入缓存
  83.                 _cache![index][target] = getResult(index: index + 1, target: target);
  84.                 // 返回结果
  85.                 return _cache![index][target];
  86.             }
  88.             // 否则，尝试选择该元素，剩余目标数 = 当前目标数 - 当前元素
  89.             let residue = target - _arr[index];
  90.             // 继续后面的元素，并传入剩余目标数，表示选择该元素
  91.             let reslut = getResult(index: index + 1, target: residue);
  92.             // 判断选择该元素之后的结果
  93.             if(reslut == 0){
  94.                 // 无法分割出相等的子集，证明该元素不符合加入子集的条件。跳过该元素，继续后面的元素
  95.                 // 将结果写入缓存
  96.                 _cache![index][target] = getResult(index: index + 1, target: target);
  97.                 // 返回结果
  98.                 return _cache![index][target];
  99.             }
  101.             // 可以分割出相等的子集
  102.             // 将结果写入缓存
  103.             _cache![index][target] = reslut;
  104.         }
  106.         // 返回结果
  107.         return _cache![index][target];
  108.     }
  109. }

2.3 递推解法

使用自底向上的递推法，创建一张集合大小 * (目标数 + 1)的表格。先解决分解后的子问题，从而解决整体问题

  1. class Solution {
  3.     fileprivate var _arr : [Int];
  5.     init(arr : [Int]) {
  6.         _arr = arr;
  7.     }
  9.     // 集合元素总和的一半，作为目标值
  10.     fileprivate var _target : Int = 0;
  11.     // 创建表格
  12.     fileprivate var _list : [[Int]]?;
  14.     func canPartition() -> Bool {
  16.         // 集合中元素个数小于2个
  17.         if(_arr.count < 2){
  18.             // 不可能分割
  19.             return false;
  20.         }
  22.         // 元素总和
  23.         var sum = 0;
  24.         // 最大元素
  25.         var maxItem = 0;
  26.         // 遍历集合中所有元素
  27.         for i in _arr {
  28.             // 累加总和
  29.             sum += i;
  30.             // 计算出最大元素
  31.             maxItem = max(i, maxItem);
  32.         }
  34.         // 判断总和为奇数
  35.         if(sum % 2 == 1) {
  36.             // 奇数，不可能分割出相等的子集
  37.             return false;
  38.         }
  40.         // 目标的结果数，即：总和取半
  41.         let target = sum / 2;
  43.         // 判断最大元素是否超过目标数
  44.         if(maxItem > target){
  45.             // 超过，不可能分割出相等的子集
  46.             return false;
  47.         }
  49.         // 初始化表格大小
  50.         _list = [[Int]](repeating: [Int](repeating: 0, count: target + 1), count: _arr.count);
  52.         // 是否可分割出等和的子集
  53.         let reslut = getResult(target: target);
  54.         // 返回结果
  55.         return reslut == 1;
  56.     }
  58.     // 是否可分割出等和的子集
  59.     func getResult(target : Int) -> Int {
  61.         // 设置初始列默认为1，当剩余目标数减到0，说明该元素可选取
  62.         for i in 0..<_arr.count {
  63.             _list![i][0] = 1;
  64.         }
  66.         // 第0行，只有初始元素可选取
  67.         _list![0][_arr[0]] = 1;
  69.         // 遍历元素
  70.         for i in 1..<_arr.count {
  72.             // 获取当前元素
  73.             let item = _arr[i];
  75.             // 遍历目标数
  76.             for j in 1...target {
  78.                 // 判断当前元素是否超过剩余的目标数
  79.                 if(item > j){
  80.                     // 超过，证明该元素不符合加入子集的条件。跳过该元素，使用上一个元素的结果覆盖当前位置
  81.                     _list![i][j] = _list![i - 1][j];
  82.                     continue;
  83.                 }
  85.                 // 否则，尝试选择该元素，剩余目标数 = 当前目标数 - 当前元素
  86.                 let residue = j - item;
  87.                 // 如果选择当前元素，在剩余目标数的情况下，获得上一个元素的结果
  88.                 let reslut = _list![i - 1][residue];
  90.                 // 判断上一个元素是否可以将剩余目标数减空
  91.                 if(reslut == 0){
  92.                     // 无法减空，证明该元素不符合加入子集的条件。跳过该元素，使用上一个元素的结果覆盖当前位置
  93.                     _list![i][j] = _list![i - 1][j];
  94.                     continue;
  95.                 }
  97.                 // 可以减空，表示该元素可以选择，它是分割相等子集的必要元素
  98.                 // 将结果写入表格
  99.                 _list![i][j] = reslut;
  100.             }
  101.         }
  103.         // 返回最终的计算结果
  104.         return _list![_arr.count - 1][target];
  105.     }
  106. }

2.4 空间优化

当前结果，只依赖于上一个元素的结果。我们可以只创建一行空间，让当前结果与上一个元素的结果共用，将空间复杂度优化为O(n)。为了不影响上一个元素的结果，目标数采用倒序遍历

  1. class Solution {
  3.     fileprivate var _arr : [Int];
  5.     init(arr : [Int]) {
  6.         _arr = arr;
  7.     }
  9.     // 集合元素总和的一半，作为目标值
  10.     fileprivate var _target : Int = 0;
  11.     // 当前行，当前结果与上一个元素的结果共用
  12.     fileprivate var _row : [Int]?;
  14.     func canPartition() -> Bool {
  16.         // 集合中元素个数小于2个
  17.         if(_arr.count < 2){
  18.             // 不可能分割
  19.             return false;
  20.         }
  22.         // 元素总和
  23.         var sum = 0;
  24.         // 最大元素
  25.         var maxItem = 0;
  26.         // 遍历集合中所有元素
  27.         for i in _arr {
  28.             // 累加总和
  29.             sum += i;
  30.             // 计算出最大元素
  31.             maxItem = max(i, maxItem);
  32.         }
  34.         // 判断总和为奇数
  35.         if(sum % 2 == 1) {
  36.             // 奇数，不可能分割出相等的子集
  37.             return false;
  38.         }
  40.         // 目标的结果数，即：总和取半
  41.         let target = sum / 2;
  43.         // 判断最大元素是否超过目标数
  44.         if(maxItem > target){
  45.             // 超过，不可能分割出相等的子集
  46.             return false;
  47.         }
  49.         // 初始化当前行
  50.         _row = [Int](repeating: 0, count: target + 1);
  52.         // 是否可分割出等和的子集
  53.         let reslut = getResult(target: target);
  54.         // 返回结果
  55.         return reslut == 1;
  56.     }
  58.     // 是否可分割出等和的子集
  59.     func getResult(target : Int) -> Int {
  61.         // 当剩余目标数减到0，说明该元素可选取
  62.         _row![0] = 1;
  63.         // 默认只有初始元素可选取
  64.         _row![_arr[0]] = 1;
  66.         // 遍历元素
  67.         for i in 1..<_arr.count {
  69.             // 获取当前元素
  70.             let item = _arr[i];
  72.             // 为了不影响上一个元素的结果，倒序遍历目标数
  73.             for j in (1...target).reversed() {
  75.                 // 判断当前元素是否超过剩余的目标数
  76.                 if(item > j){
  77.                     // 超过，证明该元素不符合加入子集的条件。跳过该元素，延用上一个元素的结果
  78.                     continue;
  79.                 }
  81.                 // 否则，尝试选择该元素，剩余目标数 = 当前目标数 - 当前元素
  82.                 let residue = j - item;
  83.                 // 如果选择当前元素，在剩余目标数的情况下，获得上一个元素的结果
  84.                 let reslut = _row![residue];
  86.                 // 判断上一个元素是否可以将剩余目标数减空
  87.                 if(reslut == 0){
  88.                     // 无法减空，证明该元素不符合加入子集的条件。跳过该元素，延用上一个元素的结果
  89.                     continue;
  90.                 }
  92.                 // 可以减空，表示该元素可以选择，它是分割相等子集的必要元素
  93.                 // 将结果覆盖
  94.                 _row![j] = reslut;
  95.             }
  96.         }
  98.         // 返回最终的计算结果
  99.         return _row![target];
  100.     }
  101. }