[算法]-双指针法常见使用场景

2sum 和 3sum

LeetCode第15题3sum：


这个题和2sum一样的思路，用双指针方法来解，这个方法一般是在有序数组中使用，一个放首，一个放尾，同时向中间遍历，直到两个指针相交，完成遍历，时间复杂度也是O(n)。

3sum问题转为2sum问题，选定第一个数字i，在剩下的元素中寻找和为-i的两个元素。

java做法：

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res= new ArrayList<>();
        Arrays.sort(nums);
        if(nums.length<3||nums[0]>0||nums[nums.length-1]<0)
            return res;
        if(nums[0]==0&&nums[nums.length-1]==0)
        {
             res.add(Arrays.asList(0,0,0));
             return res;
        }
        for(int i=0;i<nums.length-2;i++){
            int x=i+1,y=nums.length-1;
            while(y>x)
            {
                if((nums[x]+nums[y])>-nums[i])
                    y--;
                else if((nums[x]+nums[y])<-nums[i])
                    x++;
                else
                {
                    List tmp = Arrays.asList(nums[i],nums[x],nums[y]);
                    if(!res.contains(tmp))
                    {
                        res.add(tmp);
                    }
                    x++;
                }
            }
        }
        return res;
    }
}

最大的水容量

leetcode第11题

寻找最大的容量，容量等于宽*高，遍历所有的宽度可能。两个指针从做和右出发，此时宽最大，计算容量，容量取决于最矮的木板，为了寻找更大的容量需要将更短的替换，前进。

java做法：

import java.util.*;
class Solution {
    public int maxArea(int[] height) {
        int max=0;
        int vol=0;
        int i =0;
        int j = height.length-1;
        while(j>i){
            vol = Math.min(height[i],height[j])*(j-i);
            if(height[i]<height[j])
                i++;
            else
                j--;
            
            if(vol>max)
                max = vol;
        }
        return max;
    }
}

寻找单链表的中间元素

用两个指针同时从链表头部出发，指针一每次移动2，指针二每次移动1，当指针一的货指针一的next为null时，指针二的元素就是中间元素。

快排的划分

快速排序每次将一个元素放到合适的位置，并保证该位置左边都小于该元素，右边都大于该元素。

private static<T extends Comparable<T>> int partition(T[] list, int lo, int hi){
    int i = lo, j = hi;
    while (i<j){
        if (list[j].compareTo(list[lo])<=0){
            i++;
            if (list[i].compareTo(list[lo])>=0){
                exchange(list,i,j);
            }
        }
        else
            j--;
    }
    exchange(list,i,lo);
    return i;
}

将数组划分成左边奇数右边偶数

和上边快排类似，都属于in place 交换，数组的in place(就地)交换一般得用双指针，不然数组中添加或删除一个元素，需要移动大量元素。
这时候，一般是一个指针遍历，一个指针去找可以用来交换的元素。

int i = 0, j = list.length-1;
  while (i<j){
      while (i<j &&list[i]%2==0) i++;
      while (i<j &&list[j]%2==1) j--;
      if(i<j)
      {
          int temp = list[i];
          list[i] = list[j];
          list[j] = temp;
      }


  }

从后删除链表第n个元素

.png)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p1 = dummy, p2 = dummy;
        int i=0;
        while(p1!=null&&i<n+1)
        {
            p1=p1.next;
            i++;
        }
        while(p1!=null){
            p2=p2.next;
            p1=p1.next;
        }
        p2.next = p2.next.next;
        return dummy.next;
    }
}

会继续补充