1.二分查找
力扣题目链接:704. 二分查找 - 力扣(LeetCode) (leetcode-cn.com)
3.题目描述
解题思路
1. 这道题给的要求很明显 一个有序的数组,我们还可以发现这个数组中的元素是不重复的
2.因为二分查找的话返回的元素下标可能不是唯一的,这些都是用二分的前提条件
3.我们定义target在左闭右开的区间里 也就是 题目的[left,right] 当while(left<=right)的时候
因为left=right是有意义的
源码附上:
class Solution { public int search(int[] nums, int target) { int left=0; int right=nums.length-1; while(left<=right){ int mid=left+(right-left)/2; //这里防止溢出 等同于(left+right)/2 if(target>nums[mid]){ //这里target在右区间 所以left=mid+1 left=mid+1; } else if(target<nums[mid]){ //这里target在左区间 所以right=mid-1 right=mid-1; } else if(target==nums[mid]){ //target ==nums[mid]的时候也就是找到目标值的时候返回下标 return mid; } } return -1; //否则返回-1 } }
2.反转字符串
题目链接 344. 反转字符串 - 力扣(LeetCode) (leetcode-cn.com)
题目描述:
解题思路:
本题是一道经典的双指针 题目
用left指向字符数组首元素
用right指向字符数组尾元素
跑一个交换一个 直到跑到中间为止
代码附上:
class Solution { public void reverseString(char[] s) { int left=0; int right=s.length-1; while(left<right){ //左边元素小于右边元素时 ,交换俩俩元素 char tmp=s[left]; s[left]=s[right]; s[right]=tmp; left++; // 左边元素往右边走 right--; //右边元素往左边走 } } }
3.长度最小的子数组
题目链接:209. 长度最小的子数组 - 力扣(LeetCode) (leetcode-cn.com)
题目描述 :
解题思路:
这道题 可以用暴力解法 两个for循环,然后不断的寻找符合条件的连续子数组 但是时间复杂度为O(n^2)
小王同学 想到了滑动窗口的解法 :
我们先定义两个指针 left 和right,将区间看成[left,right]看成一个滑动窗口,left表示窗口开始
的位置 right表示窗口结束的位置,同时我们在初始化一个sum变量来保存区间的和
然后枚举整个数组 每次向右滑动窗口 注意在滑动窗口的同时也要收缩窗口
最后收缩的窗口区间依旧满足
代码实现:
class Solution { public int minSubArrayLen(int target, int[] nums) { int sum=0; int left=0;//窗口开始的位置 int res=Integer.MAX_VALUE;//最大值 for(int right=0;right<nums.length;right++){ //枚举整个区间 sum+=nums[right]; //向右扩展窗口 while(sum>=target){ res=Math.min(res,right-left+1);//区间更新 sum-=nums[left++]; 向左收缩窗口 } } return res==Integer.MAX_VALUE?0:res; //按条件返回 } }
以上就是我给友友们带来的几道 数组类的题 希望对大家有所帮助