面试算法大全-双指针技巧总结

本是古典何须时尚 2022-10-06 13:58 158阅读 0赞

## 16、 双指针技巧 ##

双指针具体就是用两个变量动态存储两个或多个结点，来方便我们进行一些操作。通常用在线性的数据结构中，比如链表和数组。常用的双指针思想有：快慢指针、碰撞指针、滑动窗口等。

##### 15.2.1 左右指针 #####

//nums 数组中查找target的位置
    public int searchInsert(int[] nums, int target) {
        
            int left = 0, right = nums.length - 1;
            while(left <= right) {
        
                int mid = (left + right) / 2;
                if(nums[mid] == target) {
        
                    return mid;
                } else if(nums[mid] < target) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    
    //反转数组
    public int[] reverse(int[] nums){
        
        int left=0;
        int right=nums.length-1;
        while(left<right){
        
            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
            left++;
            right++;
        }
        return nums;
    }

##### 15.2.2 快慢指针 #####

//移除元素，返回新数组长度
    //给定 nums = [3,2,2,3], val = 3,
    //函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
    public int removeElement(int[] nums,int val){
        
        int fast=0;
        int slow=0;
        while(fast<nums.length){
        
            if(nums[fast]!=val){
        
                nums[slow]=nums[fast];
                slow++;
            }
           fast++;
        }
        return slow;
    }
    
    //双指针去重  
    //给定 nums = [0,0,1,1,1,2,2,3,3,4],
    //函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
    int removeDuplicates(int[] nums) {
        
        if (nums.length == 0) {
        
            return 0;
        }
        int slow = 0, fast = 0;
        while (fast < nums.length) {
        
            if (nums[fast] != nums[slow]) {
        
                slow++;
                // 维护 nums[0..slow] 无重复
                nums[slow] = nums[fast];
            }
            fast++;
        }
        // 数组长度为索引 + 1
        return slow + 1;
    }

#### [盛最多水的容器][Link 1] ####

暴力求解

public int maxArea(int[] height) {
        
        int maxarea = 0;
        int area = 0;
        int length = height.length;
        for (int i = 0; i < length - 1; i++) {
        
            for (int j = i + 1; j < length; j++) {
        
                area = Math.min(height[i], height[j]) * (j - i);
                maxarea = Math.max(maxarea, area);
            }
        }
        return maxarea;
    }

最简形式

class Solution {
        
        public int maxArea(int[] height) {
        
            int i = 0, j = height.length - 1, res = 0;
            while(i < j){
        
                res = height[i] < height[j] ? Math.max(res, (j - i) * height[i++]): Math.max(res, (j - i) * height[j--]); 
            }
            return res;
        }
    }

双指针求解

public int maxArea(int[] height) {
        
        int maxarea = 0, left = 0, length = height.length;
        int area;
        int right;
        //从前面开始找
        while (left < length) {
        
            right = length - 1;
            while (right > left) {
        
                if (height[right] < height[left]) {
        
                    right--;
                } else {
        
                    break;
                }
            }
            //计算矩形的面积
            area = height[left] * (right - left);
            //保存计算过的最大的面积
            maxarea = Math.max(maxarea, area);
            left++;
        }
        //从后面开始找，和上面类似
        right = length - 1;
        while (right > 0) {
        
            left = 0;
            while (right > left) {
        
                if (height[right] > height[left]) {
        
                    left++;
                } else {
        
                    break;
                }
            }
            area = height[right] * (right - left);
            maxarea = Math.max(maxarea, area);
            right--;
        }
        return maxarea;
    }

双指针优化

public int maxArea(int[] height) {
        
        int maxarea = 0, left = 0, right = height.length - 1;
        int area = 0;
        while (left < right) {
        
            //计算面积，面积等于宽*高，宽就是left和right之间的距离，高就是
            //left和right所对应的最低高度
            area = Math.min(height[left], height[right]) * (right - left);
            //保存计算过的最大的面积
            maxarea = Math.max(maxarea, area);
            //柱子矮的往中间靠
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return maxarea;
    }

#### [接雨水][Link 2] ####

三指针求解

public int trap(int[] height) {
        
        if (height.length <= 2)
            return 0;
        //找到最高的柱子的下标
        int max = Integer.MIN_VALUE;
        int maxIndex = -1;
        for (int i = 0; i < height.length; i++) {
        
            if (height[i] > max) {
        
                max = height[i];
                maxIndex = i;
            }
        }
    
        //统计最高柱子左边能接的雨水数量
        int left = height[0];
        int right = 0;
        int water = 0;
        for (int i = 1; i < maxIndex; i++) {
        
            right = height[i];
            if (right > left) {
        
                left = right;
            } else {
        
                water += left - right;
            }
        }
    
        //统计最高柱子右边能接的雨水数量
        right = height[height.length - 1];
        for (int i = height.length - 2; i > maxIndex; i--) {
        
            left = height[i];
            if (height[i] > right) {
        
                right = left;
            } else {
        
                water += right - left;
            }
        }
    
        //返回盛水量
        return water;
    }

双指针求解

public int trap(int[] height) {
        
        if (height.length <= 2)
            return 0;
        int water = 0;
        int left = 0, right = height.length - 1;
        //最开始的时候确定left和right的边界，这里的left和right是
        //柱子的下标，不是柱子的高度
        while (left < right && height[left] <= height[left + 1])
            left++;
        while (left < right && height[right] <= height[right - 1])
            right--;
    
        while (left < right) {
        
            int leftValue = height[left];
            int rightValue = height[right];
            //在left和right两根柱子之间计算盛水量
            if (leftValue <= rightValue) {
        
                //如果左边柱子高度小于等于右边柱子的高度，根据木桶原理，
                // 桶的高度就是左边柱子的高度
                while (left < right && leftValue >= height[++left]) {
        
                    water += leftValue - height[left];
                }
            } else {
        
                //如果左边柱子高度大于右边柱子的高度，根据木桶原理，
                // 桶的高度就是右边柱子的高度
                while (left < right && height[--right] <= rightValue) {
        
                    water += rightValue - height[right];
                }
            }
        }
        return water;
    }
    
    
    //三个while循环合并
    public int trap(int[] height) {
        
        int left = 0;
        int right = height.length - 1;
        int water = 0;
        int leftmax = 0;
        int rightmax = 0;
        while (left < right) {
        
            //确定左边的最高柱子
            leftmax = Math.max(leftmax, height[left]);
            //确定左边的最高柱子
            rightmax = Math.max(rightmax, height[right]);
            //那么桶的高度就是leftmax和rightmax中最小的那个
            if (leftmax < rightmax) {
        
                //桶的高度是leftmax
                water += (leftmax - height[left++]);
            } else {
        
                //桶的高度是rightmax
                water += (rightmax - height[right--]);
            }
        }
        return water;
    }

双指针代码简化

public int trap(int[] height) {
        
        int left = 0, right = height.length - 1, water = 0, bucketHeight = 0;
        while (left < right) {
        
            //取height[left]和height[right]的最小值
            int minHeight = Math.min(height[left], height[right]);
            //如果最小值minHeight大于桶的高度bucketHeight，要更新桶的高度到minHeight
            bucketHeight = bucketHeight < minHeight ? minHeight : bucketHeight;
            water += height[left] >= height[right] ? (bucketHeight - height[right--]) : (bucketHeight - height[left++]);
        }
        return water;
    }

#### [无重复字符的最长子串][Link 3] ####

双指针求解

public int lengthOfLongestSubstring(String s) {
        
        if (s.length() == 0){
        
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        for (int i = 0, j = 0; i < s.length(); ++i) {
        
            //如果有重复的，就修改j的值
            if (map.containsKey(s.charAt(i))) {
        
                j = Math.max(j, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            //记录查找的最大值
            max = Math.max(max, i - j + 1);
        }
        //返回最大值
        return max;
    }

使用队列求解

public int lengthOfLongestSubstring(String s) {
        
        //用链表实现队列，队列是先进先出的
        Queue<Character> queue = new LinkedList<>();
        int max = 0;
        for (char c : s.toCharArray()) {
        
            while (queue.contains(c)) {
        
                //如果有重复的，队头出队，这里通过while循环，
                //如果还有重复的就继续出队，直到队列中没有
                // 重复的元素为止
                queue.poll();
            }
            //添加到队尾
            queue.add(c);
            //记录下最大长度
            max = Math.max(max, queue.size());
        }
        return max;
    }

#### [旋转链表][Link 4] ####

public ListNode rotateRight(ListNode head, int k) {
        
        if (head == null)
            return head;
        ListNode fast = head, slow = head;
        //链表的长度
        int len = 1;
        //统计链表的长度，顺便找到链表的尾结点
        while (fast.next != null) {
        
            len++;
            fast = fast.next;
        }
        //首尾相连，先构成环
        fast.next = head;
        //慢指针移动的步数
        int step = len - k % len;
        //移动步数，这里大于1实际上是少移了一步
        while (step-- > 1) {
        
            slow = slow.next;
        }
        //temp就是需要返回的结点
        ListNode temp = slow.next;
        //因为链表是环形的，slow就相当于尾结点了，
        //直接让他的next等于空
        slow.next = null;
        return temp;
    }

#### [环形链表][Link 5] ####

public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            if (head == null || head.next == null) {
        
                return false;
            }
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast) {
        
                if (fast == null || fast.next == null) {
        
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/container-with-most-water/
[Link 2]: https://leetcode-cn.com/problems/trapping-rain-water/
[Link 3]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[Link 4]: https://leetcode-cn.com/problems/rotate-list/
[Link 5]: https://leetcode-cn.com/problems/linked-list-cycle/