这里的双指针用法和LeetCode11题很像

LeetCode 11. LeetCode11-盛最多水的容器-20200608-java

思路

• 1 先排序, 准备手写快速排序或归并排序
• 2 定义三个指针: $t,l,r$.
  • 2.1 $t$ 是遍历数组的指针,对于每一个 $t$,
    • 2.1.1 初始化 $l=t+1$, $r=nums.length-1$;
    • 2.1.2 $[l,r]$ 区间检测,直到 $l>=r$ 为止.
      • 2.1.2.1 $nums[l] + nums[r] + nums[t] == 0$, $l$向右无重复移动(无重复需要判断), $r向左无重复移动(无重复需要判断)
      • 2.1.2.2 $nums[l] + nums[r] + nums[t] < 0$, 说明需要增大某一个数, 于是$l$右移
      • 2.1.2.3 $nums[l] + nums[r] + nums[t] > 0$, 说明需要减小某一个数, 于是$r$左移
  • 2.2 边界处理, 如果$nums[t] == nums[t-1]$, 说明$nums[t]$已经参与过计算, 需要剪枝.

java

class Solution {

    public List<List<Integer>> threeSum(int[] nums) {
        // 先排序, nlog(n)
        quickSort(nums, 0, nums.length-1);
        List<List<Integer>> res = new ArrayList<>();

        //三个指针: t固定, l为t右侧第一个数, r为数组最右侧的数
        for(int t = 0; t < nums.length; t++){
            //如果t与t+1相同,进行剪枝
            while(t != 0 && t < nums.length && nums[t-1] == nums[t]) t++;
            //while写成if似乎占用空间小一些, 运行时间没有区别. 
            //if(t != 0 && t < nums.length && nums[t-1] == nums[t]) continue;
            int l = t + 1, r = nums.length-1;
            while(l < r){
                if(nums[l] + nums[r] + nums[t] == 0) {
                    //相等添加结果
                    List<Integer> tmp  = new ArrayList();
                    tmp.add(nums[t]);
                    tmp.add(nums[l]);
                    tmp.add(nums[r]);
                    res.add(tmp);
                    // 如果t,l, r的和==0, 那么需要判断l和r的移动, l右移到不重复位置
                    do l++; while(l < nums.length && nums[l-1] == nums[l]);
                    // r左移到不重复位置
                    do r--; while(r > 0 && nums[r+1] == nums[r]);
                }else if(nums[l] + nums[r] + nums[t] < 0){
                    l++; 
                }else{
                    r--;
                }
            }
        }

        return res;
    }

    //顺便复习一下快排
    public void quickSort(int[] nums, int l, int r){
        if(l >= r) return;

        // int mid = l+r>>1;
        int x = nums[l+r>>1];
        int i = l-1, j = r+1;
        while(i < j){
            while(nums[++i] < x);
            while(nums[--j] > x);
            if(i < j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }

        quickSort(nums, l, j);
        quickSort(nums, j+1, r);
    }

    // 归并排序 
    public void mergeSort(int[] nums, int[] tmp, int l, int r){
        if(l >= r) return;

        int mid = l + r >> 1;
        mergeSort(nums, tmp, l, mid);
        mergeSort(nums, tmp, mid+1, r);

        int i = l, j = mid+1, k = 0;
        while(i < j && i <= mid && j <= r){
            if(nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else tmp[k++] = nums[j++];
        }

        while(i <= mid) tmp[k++] = nums[i++];
        while(j <= r) tmp[k++] = nums[j++];

        for(int s = l, m = 0; s <= r && m <= k; s++,m++) nums[s] = tmp[m];
    }
}