acytoo

Leetcode 1498 Number of Subsequences That Satisfy the Given Sum Condition

这道题给了一个数组，要求出有多少个满足条件的子序列，这个要求是子序列中的最大值与最小值的和，不能超过target

因为只与子序列中的最大值与最小值有关，与序列中数字的顺序无关，我们可以先排序，然后使用（贪心）（双指针）来解决这个问题。

举一个例子arr = [1, 2, 3, 4, 5, 6, 7], target = 7，首先排序，然后发现最小值1与最大值6时，满足条件1 + 6 <= 7， 则1与6之间的4个数字，可以随便取。则所有可能的情况是${c_4}^1 + {c_4}^2 + {c_4}^3 + {c_4}^4 = 2^4$。然后发现最小值是1，最大值是5时，也满足情况，所以继续上一步中的过程。

然后，超过了int的表示范围，超过了lang的表示范围，超过了long long的表示范围。

class Solution_Runtime_error {  // out of range long long
 public:
  int numSubseq(vector<int>& nums, int target) {
    constexpr int kMod = 1e9  + 7;
    long long res = 0;
    sort(nums.begin(), nums.end());  // order doesn't matter
    for (int i = 0, n = nums.size(); i < n; ++i) {
      for (int j = n - 1; j >= i; --j) {
        if (nums[i] + nums[j] > target) continue;
        if (i == j)
          res += 1;
        else
          res = (res + static_cast<long long>(pow(2, (j - i - 1)))) % kMod;
      }
    }
    return res % kMod;
  }
};

最后上网搜索大神们的解决方法，下面这个ac的方法来自huahua

static int x = [] () {ios::sync_with_stdio(false); cin.tie(0); return 0;} ();
// From huahua
class Solution {
 public:
  int numSubseq(vector<int>& nums, int target) {
    constexpr int kMod = 1e9  + 7;
    const int n = nums.size();
    sort(nums.begin(), nums.end());  // order doesn't matter
    vector<int> pows(n + 1, 1);
    for (int i = 1; i <= n; ++i) pows[i] = (pows[i - 1] << 1) % kMod;
    int res = 0;
    for (int i = 0, j = n - 1; i <= j; ++i) {
      while (i <= j && nums[i] + nums[j] > target) --j;
      if (i > j) continue;
      res = (res + pows[j - i]) % kMod;
    }
    return res;
  }
};
#直达链接

LeetCode 1498. Number of Subsequences That Satisfy the Given Sum Condition

相关文章：