练习题 将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 <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

提交代码

//将x减到0的最小操作数

//返回最小操作数
//无解操作数为-1
//x恰好减到0
//操作数其实就是两端和为x的个数
//改良后的滑动窗口
//循环尝试使用几个最左端的操作数
//连续两段元素的群体关系 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> nums;//整数数组
int x;//目标值
int result = (int)(1e5 + 1);//最小操作数 
int n;//数组长度 

//改良后的滑动窗口
void slidingWindow(){
	int left = 0,right = n - 1;//左右指针
	int res = 0;//暂时存储操作数
	int total = 0;//暂时存储操作数之和 
	
	if(nums[left] > x && nums[right] > x){
		result = -1;
		return;
	}
	
	//初始化右指针位置
	for(;right >= 0;){
		total += nums[right];
		res++;
		
		//右指针不可能更靠左了
		if(total == x){
			//printf("left=%d,right=%d\n",left,right);
			result = min(result,res);
			break;
		}else if(total > x){
			total -= nums[right];
			right++;
			res--;
			break;
		}
		
		right--;
	}
	
	//循环尝试使用几个最左端的数
	while(left < right){
		total += nums[left];
		res++;
		
		while(total > x){
			if(right < n){
				total -= nums[right];
				right++;
				res--;
			}else{
				res--;
				break;
			}
		}
		
		if(total == x){
			//满足条件
			result = min(result,res); 
			//printf("left=%d,right=%d\n",left,right);
		}else if(total > x){
			break;
		}
		
		left++;
	}
	
	if(left >= right && right == -1){
		//无解 
		result = -1;
	}
} 

int main(){
	//输入整数数组  
	int t; 
	
	while(cin.peek() != '\n'){
		scanf("%d",&t);
		nums.push_back(t);
	}
	
	//输入目标值
	scanf("%d",&x); 
	
	//-------------------------------
	
	n = nums.size();//数组长度 
	
	//改良后的滑动窗口
	slidingWindow(); 
	
	//输出结果
	printf("%d",result);
	
	return 0;
} 

?总结

解题思路：题目中的移除最左端和最右端的元素，本质上就是两端两段连续元素的群体关系，可以使用改良后的滑动窗口（同向双指针）。先确定从右端向左最多可以取几个元素，确定右指针的初始位置，然后循环左移左指针（左端取几个元素），右移右指针（右端少用几个元素），找合理解。注意无解的可能情况有两种，一种是拿的值加起来大于x，另一种是都拿了也不够。