本文涉及的基础知识点

C++二分查找
C++前后缀分解
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

LeetCode1658. 将 x 减到 0 的最小操作数

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
示例 1：
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
示例 2：
输入：nums = [5,6,7,8,9], x = 4
输出：-1
示例 3：
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
提示：
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴
1 <= x <= 10⁹

二分查找

n = nums.length
枚举右边删除了i1($\in$[0,n])个元素,令其和为x1，则在前缀和中查找是否存在preSum[i2]=x-x1,由于nums的元素都是正数，所以最多一个解。
同时左边和右边删除的部分，不能有重复元素，即：i1+i2<=n。

代码

核心代码

class Solution {
		public:
			int minOperations(vector<int>& nums, int x) {
				const int N = nums.size();
				vector<int> preSum(1);
				for (const auto& n : nums) {
					preSum.emplace_back(n + preSum.back());
				}
				int ret = N + 1;
				for (int i = 0; i <= N; i++) {
					const int x1 = preSum.back() - preSum[N - i];
					auto it = std::equal_range(preSum.begin(), preSum.end(), x - x1);
					if (it.first == it.second) { continue; }
					ret = min(ret, (int)(it.first- preSum.begin() + i));
				}
				return ret > N ? -1 : ret;
			}
		};

单元测试

	vector<int> nums;
		int x;
		TEST_METHOD(TestMethod11)
		{
			nums = { 1, 1, 4, 2, 3 }, x = 5;
			auto res = Solution().minOperations(nums, x);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 5,6,7,8,9 }, x = 4;
			auto res = Solution().minOperations(nums, x);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 3,2,20,1,1,3 }, x = 10;
			auto res = Solution().minOperations(nums, x);
			AssertEx(5, res);
		}