Re: [閒聊] 每日leetcode
1658. Minimum Operations to Reduce X to Zero
給一個整數array : nums 和一個整數 : n
在每次操作可以移除最右邊或最左邊的數字
並且將x扣掉那個數字的值
請回傳最少的操作次數使x剛好被扣到等於0
思路:
假設array所有數字的總和為sum
其實這題換個角度想
就是在問 : 請求一個最長的subarray，該subarray所有數字的總和為sum-x
這樣就用sliding window就可以解決了
c++ :
class Solution {
public:
int minOperations(vector<int> &nums, int x)
{
int sum = 0, n = nums.size(), target = 0, start = 0, cnt = 0;
target = accumulate(nums.begin(), nums.end(), 0) - x;
if (target == 0) {
return n;
}
for (int i = 0; i < n; i++) {
sum += nums[i];
while (start < i && sum > target) {
sum -= nums[start];
start++;
}
if (sum == target) {
cnt = max(cnt, i - start + 1);
}
}
if (cnt == 0) {
return -1;
}
return n - cnt;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1750254077.A.261.html
推
06/18 21:47,
5月前
, 1F
06/18 21:47, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1448 之 1548 篇)：