Subarray Sum Closest

Question

  1. Given an integer array, find a subarray with sum closest to zero.
  2. Return the indexes of the first number and last number.
  4. Example
  5. Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4]
  7. Challenge
  8. O(nlogn) time

题解

题 Zero Sum Subarray | Data Structure and Algorithm 的变形题，由于要求的子串和不一定，故哈希表的方法不再适用，使用解法4 - 排序即可在 O(n \log n) 内解决。具体步骤如下：

  1. 首先遍历一次数组求得子串和。
  2. 对子串和排序。
  3. 逐个比较相邻两项差值的绝对值，返回差值绝对值最小的两项。

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param nums: A list of integers
  5.      * @return: A list of integers includes the index of the first number
  6.      *          and the index of the last number
  7.      */
  8.     vector<int> subarraySumClosest(vector<int> nums){
  9.         vector<int> result;
  10.         if (nums.empty()) {
  11.             return result;
  12.         }
  14.         const int num_size = nums.size();
  15.         vector<pair<int, int> > sum_index(num_size + 1);
  17.         for (int i = 0; i < num_size; ++i) {
  18.             sum_index[i + 1].first = sum_index[i].first + nums[i];
  19.             sum_index[i + 1].second = i + 1;
  20.         }
  22.         sort(sum_index.begin(), sum_index.end());
  24.         int min_diff = INT_MAX;
  25.         int closest_index = 1;
  26.         for (int i = 1; i < num_size + 1; ++i) {
  27.             int sum_diff = abs(sum_index[i].first - sum_index[i - 1].first);
  28.             if (min_diff > sum_diff) {
  29.                 min_diff = sum_diff;
  30.                 closest_index = i;
  31.             }
  32.         }
  34.         int left_index = min(sum_index[closest_index - 1].second,\
  35.                              sum_index[closest_index].second);
  36.         int right_index = -1 + max(sum_index[closest_index - 1].second,\
  37.                                    sum_index[closest_index].second);
  38.         result.push_back(left_index);
  39.         result.push_back(right_index);
  40.         return result;
  41.     }
  42. };

源码分析

为避免对单个子串和是否为最小情形的单独考虑，我们可以采取类似链表 dummy 节点的方法规避，简化代码实现。故初始化sum_index时需要num_size + 1个。这里为避免 vector 反复扩充空间降低运行效率，使用resize一步到位。sum_index即最后结果中left_index和right_index等边界可以结合简单例子分析确定。

复杂度分析

  1. 遍历一次求得子串和时间复杂度为 $$O(n)$$, 空间复杂度为 $$O(n+1)$$.
  2. 对子串和排序，平均时间复杂度为 $$O(n \log n)$$.
  3. 遍历排序后的子串和数组，时间复杂度为 $$O(n)$$.

总的时间复杂度为 O(n \log n), 空间复杂度为 O(n).

扩展