find longest subarray closest/equal to k

find_longest_subarray_closest_to_k.cpp

pair<int, int> FindSubarrayClosestToK(const vector<int>& a, int k) {
  pair<int, int> range{0, -1};

  if (a.empty()) return range;

  map<int, int> sum_to_idx;
  int sum = 0;
  int min_diff = k;
  sum_to_idx.emplace(0, -1); // S[-1] = 0 so push 0, -1 here!
  for (int i = 0; i < a.size(); ++i) {
    sum += a[i];
    auto it = sum_to_idx.upper_bound(sum - k); // -> use sum[i] - k < sum[j] + upperbound for map!
    // because sum[i] - sum[j] < k, we want to find smallest sum[j], we find upperbound for
    // sum[i] - k !!!!!
    if (it != sum_to_idx.end() && k - sum < min_diff) {
      range = {it->second + 1, i};
      min_diff = k - sum;
    }
    sum_to_idx.emplace(sum, i);
  }
  return range;
}

find_longest_subarray_equal_to_k.cpp

typedef pair<int, int> Range;
Range FindSubarrayWithSum(const vector<int>& a, int k) {
  Range result{ -1, -1};
  if (a.empty())
    return result;
  unordered_map<int, int> sum_to_idx;
  int sum = 0;
  sum_to_idx.emplace(sum, -1); // cumulative sum at -1 is 0
  for (int i = 0; i < a.size(); ++i) {
    sum += a[i];
    auto it = sum_to_idx.find(sum - k);
    if (it != sum_to_idx.end()) {
      return {it->second + 1, i};  // j + 1 -> i
    }
    sum_to_idx.emplace(sum, i);
  }
  return result;
}