双指针+滑动窗口

简介: 双指针+滑动窗口

力扣611有效的三角形个数


暴力法:

for(i=0;i<n;i++)    

for(j=i+1;j<n;j++)

for(k=j+1;k<n;k++)

check(i,j,k)

数组有序,来判断(因为只要是最小的数字,两个相加都干不过那个大数,那么就肯定不是三角形了。

法二:

利用单调性(排序),使用双指针算法解决问题。

class Solution {
    public static int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int end=nums.length-1;
        int sum=0;
        while(end>=2){
//内部还要有一个循环,让最后一个固定的数字也来变化
            int left=0;
            int right=end-1;
//注意right是在end的左边,不是他自己单独出来
            while(left<right&&end>=2){
 
            if(nums[left]+nums[right]<=nums[end])
                left++;
            else{
                sum+=right-left;
                right--;
            }
            }
                end--;
        }
        return sum;
    }
}

力扣209长度最小子数组

什么叫滑动窗口:听起来像是一个噱头,其实就是简单的相同方向的双指针

当两个指针都不会退,利用单调性

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
     int left=0;
     int ret=Integer.MAX_VALUE;
     int right=0;
         int sum=0;
     int m=nums.length;
 
     while(right<m){
//注意考虑这个为什么在内层循环的外面,是因为内层是看他是否大于的,外层是对于他小于的情况下,进行的操作。
       sum+=nums[right];
         while(sum>=target){
//这个循环是看他什么时候比target大于(因为只需要一个就行,再往后下一个会更长,所以这个短的看可不可以,要是可以,就不需要看长的了
             ret=Math.min(ret,right-left+1);
//发现大于了之后,要更改最小记录,然后移动指针,并且sum减去left指针指定的数字
             sum-=nums[left];
             left++;
         }
//假如发现小于了,right向右移动,然后sum+
         right++;
     }
     if(ret==Integer.MAX_VALUE){
         ret=0;
     }
  return ret;
    } 
}

力扣3.无重复字符的最长子串

子串:字符串中连续的部分

子数组:数组中连续的部分呢

1.暴力枚举+哈希表(判断字符是否重复出现)

当发现区间内有重复字符,跳过重复的字符后面(right不用往后走,同时像一个方向移动)

2.利用规律,使用滑动窗口解决问题

1.left=0,right=0

2.进窗口(字符进入哈希表)

3.判断(窗口内出现重复字符)

4.出窗口(从哈希表中删除该字符)

更新结果(注意,这个过程,不是一定在这里,有的事出窗口之前,有的是出窗口之后)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        char []ss=s.toCharArray();
        int n=s.length();
       // 用数组模拟哈希
        int []hash=new int[128];//可以用ASCll  0位置下标为0,表示ASCll为0的出现的0次
     int left=0;
     int right=0;
     int len=0;
     while(right<n){
      //看是否重复的这一步不会写
      //(这一步是hash表里面,把ss[right]的值加加,也就是入窗口)
      hash[ss[right]]++;
      //然后进行判断,看是否出现重复字符(我们日常思维就是往回一起看,有没有相同的,但是编程的思维就是一个一个的去看是否有相同的)
      while(hash[ss[right]]>1){
          //把这个left移除,然后left++(相当于市发现有重复的了,然后把左边的去掉,然后注意她是一个循环,一直去掉直到不重复为止)
            hash[ss[left]]--; 
            left++; }//出窗口
            len=Math.max(len,right-left+1);
            right++;//让下一个字符进入窗口
     }
 
return len;
    }
}

力扣1004.最大连续1的个数III

题目难点:

假如说按照他那个真的要翻转,那么我们遍历下一组的时候,就还需要把它给还原回来,这就很麻烦

换一种思路想:找最长的子数组,在这个子数组中不能出现多于k个0。

class Solution {
    public int longestOnes(int[] nums, int k) {
    int left=0;
    int right=0;
    int ret=0;
   // zero计数器
    int count=0;
    int n=nums.length;
    while(right<n){
       if(nums[right]==0){
           count++;
       }
//注意哈,这里是不能加上left<right的,我原先以为这个是可写可不写,后来发现,必须不能写
因为left可以大于right ,1010 k=0假如这样,right=1(处于0的位置) ,然后left就开始移动,它是会一直动,动到不是0,也就是第三个位置(1),此时left就会大于right,所以不能加上left<right
        while(count>k){
          if(nums[left]==0){
              count--;    }
              left++;}
       ret=Math.max(ret,right-left+1);
       right++;
    }
   
    return ret;
    }   
}


相关文章
|
6月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
6月前
|
算法 容器 NoSQL
双指针扫描、滑动窗口
双指针扫描、滑动窗口
|
5月前
|
Go C++
代码随想录——双指针/滑动窗口(二)
代码随想录——双指针/滑动窗口(二)
|
5月前
|
Go C++
代码随想录——双指针与滑动窗口(四)
代码随想录——双指针与滑动窗口(四)
|
5月前
|
Go C++
代码随想录——双指针/滑动窗口(三)
代码随想录——双指针/滑动窗口(三)
|
6月前
【错题集-编程题】dd爱框框(同向双指针 / 滑动窗口)
【错题集-编程题】dd爱框框(同向双指针 / 滑动窗口)
|
6月前
|
索引
LeetCode438题(无敌双指针——滑动窗口)
LeetCode438题(无敌双指针——滑动窗口)
|
6月前
|
存储
【Leetcode 209】长度最小的子数组 —— 滑动窗口|双指针
我们可以使用双指针解决本题,定义两个指针 i 和 j 分别表示子数组(滑动窗口窗口)的开始位置和结束位置,维护变量 sum 存储子数组中的元素和。每一轮迭代中,每当 sum >= target 则记录子数组最小长度,移动慢指针。在每一轮迭代最后,移动快指针
|
人工智能 测试技术 BI
cf1348B phoenix and beauty(双指针滑动窗口)
cf1348B phoenix and beauty(双指针滑动窗口)
66 0
(双指针滑动窗口)AcWing 1238. 日志统计
(双指针滑动窗口)AcWing 1238. 日志统计
83 0