寒假刷题Day19

一、923. 三数之和的多种可能

class Solution {
public:int threeSumMulti(vector<int>& arr, int target) {const int MOD = 1'000'000'007; // 正确的模数long long ans = 0; // 使用 long long 防止溢出std::sort(arr.begin(), arr.end());for (size_t i = 0; i < arr.size(); ++i) {int T = target - arr[i];size_t j = i + 1, k = arr.size() - 1;while (j < k) {if (arr[j] + arr[k] < T) {j++;} else if (arr[j] + arr[k] > T) {k--;} else if (arr[j] != arr[k]) { int left = 1, right = 1;while (j + 1 < k && arr[j] == arr[j + 1]) {left++;j++;}while (k - 1 > j && arr[k] == arr[k - 1]) {right++;k--;}ans += static_cast<long long>(left) * right; // 避免溢出ans %= MOD;j++;k--;} else {long long M = k - j + 1;ans += (M * (M - 1) / 2) % MOD; // 避免溢出ans %= MOD;break;}}}return static_cast<int>(ans);}
};

static_cast<long>(value)在编译时进行类型转换，比c风格的(long)value更安全更清晰

二、948. 令牌放置

思路：点数小的得分，大的吃掉，当不够获得最小令牌的分时候，吃一个最大的令牌

class Solution {
public:int bagOfTokensScore(vector<int>& tokens, int P) {if (tokens.empty()) return 0;sort(tokens.begin(), tokens.end());if (P < tokens[0]) return 0;int N = tokens.size();int left = 0;int right = N - 1;int score = 0;int res = 0;while (left <= right) {if (P < tokens[left]) {if (score <= 0) return res;P += tokens[right];--score;--right;} else {P -= tokens[left];++score;++left;res = max(res, score);}}return res;}
};