数据结构与算法之双指针

java小杰要加油

发布于 2021-08-13 14:22:46

1.4K0

发布于 2021-08-13 14:22:46

文章被收录于专栏：java小杰要加油java小杰要加油

双指针

今天来通过5个力扣题来分享下数据结构与算法中的一个解题方法——双指针

26. 删除有序数组中的重复项

力扣地址：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

举个例子，大概就是想这样，最后返回4，因为有4个不同的数字

class Solution {
    public int removeDuplicates(int[] nums) {
        // 当数组为0时，返回0
        if(nums.length==0){
          return 0;  
        }
         // 定义慢指针
         int last = 0;
         // 定义快指针
         int fast = 0;
         // 当快指针没有走到末尾的时候
            while(fast<nums.length){
              // 如果慢快指针指向的数值不等于慢指针指向的数值
             if(nums[fast] != nums[last]){
               // 慢指针向前移动一位
                 last++;
                 // 将慢指针指向的数值变成快指针指向的数值
                 nums[last] = nums[fast];
             }
             //快指针向前移动一位
               fast++;
            }  
         // 返回满指针+1 这个时候就是不重复数组的长度
         return last+1;
    }
}

这其中最主要的就是

  // 当快指针没有走到末尾的时候
  while(fast<nums.length){
    // 如果慢快指针指向的数值不等于慢指针指向的数值
   if(nums[fast] != nums[last]){
     // 慢指针向前移动一位
       last++;
       // 将慢指针指向的数值变成快指针指向的数值
       nums[last] = nums[fast];
   }
   //快指针向前移动一位
     fast++;
  }

慢指针和快指针都是是从左边第一个元素开始走的
慢指针确保的是，从左边第一个元素到满指针指向的元素，这些元素不重复

当快指针没有走到末尾的时候，快指针无论如何都要向前走。

当快指针指向的数值与慢指针指向的相等的时候，这个时候就意着，数据开始重复，而我们慢指针确保的是不重复数据，那么，慢指针不动，让快指针继续向前走
当快指针指向的数值与慢指针指向的不等的时候，这个时候就意着慢指针需要向前移动，慢指针向前移动一位后，需要把此时慢指针指向的数值变成刚才那个快指针指向的数值，因为我们慢指针确保的是从最左边开始是不重复数据

具体变化如下

27. 移除元素

力扣地址：https://leetcode-cn.com/problems/remove-element/

举个例子，大概是这样

class Solution {
    public int removeElement(int[] nums, int val) {
         if(nums.length == 0){
             return 0;
         }
        int slow =0;
        int fast =0;
         // 快指针不到末尾时
         while(fast<nums.length){
             //快指针不等于需要移除的数值时
             if(nums[fast] != val){
                 //将快指针指向的数值赋值给慢指针
                nums[slow] = nums[fast];
                //慢指针继续前移
                slow ++;
             }
             //快指针移动
             fast++;
         }
         
         return slow;
    }
}

慢指针指向的数都是最终数组中的，是删除要删除的数据后的数组
当我们快指针指向要删除的数据的时候，慢指针不动，快指针前移
当我们快指针指向的不是要删除的数据的时候，将快指针指向的数值赋值给慢指针，然后慢指针向前移动一位，快指针前移

209. 长度最小的子数组

力扣地址：https://leetcode-cn.com/problems/minimum-size-subarray-sum/

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        // 窗口左边界
        int left = 0;
        // 窗口右边界
        int right = 0;
        //总和
        int sum =0;
        // 默认滑动窗口长度
        int result = Integer.MAX_VALUE;
        // 当滑动窗口右边界没到末尾的时候
        while(right <nums.length ){
            // 计算滑动窗口内的总和
            sum = sum + nums[right];
            // 当这次的总和 >= 目标值
            while(sum >=target){
                // 更新滑动窗口的长度，用上次长度和这次的滑窗长度比，取最短的
                result = Math.min(result, right- left+1);
                // 更新总和，减去左边界的值
                sum = sum - nums[left];
                // 滑动窗口左边界向右移动，收缩滑动窗口
                left++;
            }
             // 滑动窗口右边界向右移动
            right++;
        }
        // 如果result没变的话，代表没有符合条件的子数组，返回0，否则返回result  
        return result == Integer.MAX_VALUE ? 0: result;
    }
}

流程如下，主要观察图中绿色的滑动窗口的变化

487. 最大连续1的个数 II

力扣地址：https://leetcode-cn.com/problems/max-consecutive-ones-ii/

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0;
        int right = 0;
        // 0的个数 最大为1
        int zeroCount = 0;
        int result =0;
        while(right <nums.length){
            if(nums[right] == 0){
                zeroCount++;
            }
            // 0的个数大于一时 
            while(zeroCount>1){
                // 当左指针指向的数值是0的时候，0的个数减一
                if(nums[left] == 0){
                    zeroCount--;
                 }
                 // 移动左指针
                 left++;
            }
            // 更新结果
            result =  Math.max(result, right-left+1);
            //右指针移动
            right++;
        }
        return result;
    }
}

流程如下，主要观察图中绿色的滑动窗口的变化

1004. 最大连续1的个数 III

力扣地址：https://leetcode-cn.com/problems/max-consecutive-ones-iii/

这个题和上个题的唯一区别就是由一开始允许的1个0变成了K个0

代码变化也不大，就是由1变成了K,完整代码如下

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left =0;
        int right =0;
        int zeroCount =0;
        int result =0;
        while(right<nums.length){
            if(nums[right] == 0){
               zeroCount++;
            }

            while(zeroCount >k){
                if(nums[left] ==0){
                    zeroCount--;
                }
                left++;
            }
            result = Math.max(result, right - left +1);
            right++;
        }
        return result;

    }
}