医院网站建设招标说明,wordpress 大门户,嘉峪关网站seo,wordpress主题安装完后前台打不开1658 将 x 减到 0 的最小操作数 解析#xff1a;1. 当数组的两端的数都大于x时#xff0c;直接返回 -1。 2. 当数组所有数之和小于 x 时 #xff0c;直接返回 -1。 3. 数组中可以将 x 消除为0#xff0c;那么可以从左边减小为 0 #xff1b;可以从右边减小为 0 #xff1…1658 将 x 减到 0 的最小操作数 解析1. 当数组的两端的数都大于x时直接返回 -1。 2. 当数组所有数之和小于 x 时 直接返回 -1。 3. 数组中可以将 x 消除为0那么可以从左边减小为 0 可以从右边减小为 0 也可以同时从左边和右边减小为 0 。 这样分析下来这道题的第三种情况的处理会比较麻烦因为减小为 0 的区间存在不连续。 但是子区间之和 等于 总区间和 - x 的这个子区间是连续的简言之target sum -x sum等于原数组所有数之和。将该问题转化到 求最大长度和为target的连续子数组。 算法原理使用双指针 left 和 right 利用变量ret 记录子区间的和当ret target 时更新ret值并将右移left指针 更新和为target的区间长度 最后返回 数组总长度 - 和为target 区间长度。
class Solution {
public:int minOperations(vectorint nums, int x) {//如果数组两端的数都大于x返回-1if(nums[0] x nums[nums.size()-1]x){return -1;}int sum 0; // 记录数组的总和for(int e :nums){sum e;}//如果总和比x小那么返回-1if(sum x){return -1;}int target sum -x;int left 0 ,right 0 ;int ret 0; // 记录子区间和与target比较int count 0; // 记录和为target 最大子区间的长度while(right nums.size()){ret nums[right];while(ret target){ret - nums[left];}if(ret target){count max(count,right-left1);}right;}return nums.size()-count;}
};
