网站建设投诉去哪里投诉,盐城网站平台建设,网站制作排名优化,运维培训 网站建设Leetcode704:
给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff0c;否则返回 -1。 示例 1:
输入: nums [-1,0,3,5,9,12], target 9
输出:…Leetcode704:
给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。 示例 1:
输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
代码
class Solution {
public:int search(vectorint nums, int target) {sort(nums.begin(), nums.end());int l, r, mid;l 0, r nums.size();//左闭右开与结束循环条件lr相对应while (l r) {mid (l r) / 2;if (nums[mid] target) {//由于这种二分方法是利用l1避免无限循环因此rmid的判定条件是合法即可(即加上等于号)//因为r不会1会一直将搜索结果保留在区间内r mid;} else {l mid 1;}}if (l 0 l nums.size() nums[l] target)return l;elsereturn -1;}
}; Leetcode 209
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
子数组 [numsl, numsl1, ..., numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
示例 1
输入target 7, nums [2,3,1,2,4,3]
输出2
解释子数组 [4,3] 是该条件下的长度最小的子数组。典型的二分搜索答案类型题。以最终答案长度作为二分搜索的目标进行搜索。
class Solution {
public:bool check(int mid, int target, vectorint nums){int sum 0;for(int i 0;imid;i){sum nums[i];}if(targetsum)return true;for(int i mid;inums.size();i){sumnums[i];sum-nums[i-mid];if(targetsum)return true;}return false;}int minSubArrayLen(int target, vectorint nums) {int sum 0;for(int i 0;inums.size();i){sum nums[i];}if(targetsum)return 0;int l,r,mid;l 1,r nums.size();while(lr){mid(lr)/2;if(check(mid,target,nums)){r mid;}else l mid 1;}return l;}
};
这道题还可以使用双指针代码如下
class Solution {
public:int minSubArrayLen(int s, vectorint nums) {int l,r;lr0;int sum 0;int ans INT_MAX;while(rnums.size()){sum nums[r];if(sums){while(sums){sum-nums[l];l;}ans min(ans,r-l2);}r;}if(ansINT_MAX)return 0;else return ans;}
};
