双指针-多数之和

2020-06-01

双指针技巧之-多数之和

首先说明一点，这里的所要讲的双指针默认为头尾指针，那么数组一定要是有序的

167、两数之和-输入有序数组

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

我们初始化头尾指针，如果两数之和<target，让左指针往后移，如果两数之和>target，让右指针往后移.
能够这样操作的前提是一个有序数组，这样才能保证，当左指针往后移时，两数之和会变大。同理当右指针往左移时，两数之和会变小.

class Solution {
    public int[] twoSum(int[] nums, int target) {
             if(nums.length==0) return new int[]{-1,-1};
      //初始化两个指针
         int l=0,r=nums.length-1;
        while(l<r){
          //找出了解，要注意此时下标值不是从0开始的
            if(nums[l]+nums[r]==target) return new int[]{l+1,r+1};
            else if(nums[l]+nums[r]>target) r--;
            else l++;
        }
        return new int[]{-1,-1};
    }
}

15、三数之和 https://leetcode-cn.com/problems/3sum/

由于这里题目需要找出不重复的三数之和，在之前全排列2中我们介绍过一种去重的方法。
首先我们要将数组排序，这样让两个相等的数在一起，这样更能方便我们使用双指针技巧.
与之前的两数之和想法类似,不过为了先制造三个数字，我们需要在外层套用一个循环

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
           List<List<Integer>> res=new ArrayList<>();
        if(nums.length<3||nums==null) return res;
        //手动排序
        Arrays.sort(nums);
        //保证有三个数
        for(int i=0;i<nums.length-2;i++){
             int l=i+1,r=nums.length-1;
             if(i>0&&nums[i]==nums[i-1]) continue;
            while(l<r){  
       if(nums[i]+nums[l]+nums[r]==0) {
       res.add(Arrays.asList(nums[i],nums[l],nums[r]));
     //去重
      while(l<r&&nums[l]==nums[l+1]) l++;
     while(l<r&&nums[r]==nums[r-1])r--;
     l++;
     r--;
        }else if(nums[i]+nums[l]+nums[r]>0) r--;
        else l++;
            }
                
        }
        return res;
    }
}

16、最接近的三数之和 https://leetcode-cn.com/problems/3sum-closest/

与第15题三数之和类似，不过这里表达的意思是最接近的三数之和
还是跟上述一样利用双指针的思想

class Solution {
    public int threeSumClosest(int[] nums, int target) {
         if(nums==null||nums.length<3) return 0;
        Arrays.sort(nums);
        int min=nums[0]+nums[1]+nums[2];
        for(int i=0;i<nums.length-2;i++){
            int l=i+1,r=nums.length-1;
         while(l<r){
             int sum=nums[i]+nums[l]+nums[r];
             //选择最小的三数之和
             if(Math.abs(sum-target)<Math.abs(min-target)){
                 min=sum;
             }
             if(sum==target) return target;
             else if(sum>target) r--;
             else l++;
         }
        }
        return min;
    }
}

18、四数之和 https://leetcode-cn.com/problems/4sum/

有了前面做三数之和的经验，现在做四数之和，与之前的思路类似。
不过为了利用双指针，我们在外层套用两个循环
同样，本题还可以加入剪枝的思想，提前作出判断

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
         List<List<Integer>>res=new ArrayList<>();
       if(nums==null||nums.length<4) return res;
        //不要忘了排序
        Arrays.sort(nums);
        int n=nums.length;
        int minValue=nums[0]+nums[1]+nums[2]+nums[3];
        int maxValue=nums[n-1]+nums[n-4]+nums[n-3]+nums[n-2];
        if(minValue>target||maxValue<target) return res;
        for(int i=0;i<nums.length-3;i++){
            //去重
              if(i>0&&nums[i]==nums[i-1]) continue;
            for(int j=i+1;j<nums.length-2;j++){
                //去重
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                int l=j+1,r=nums.length-1;
                minValue=nums[i]+nums[j]+nums[l]+nums[l+1];
                maxValue=nums[i]+nums[j]+nums[r]+nums[r-1];
                if(minValue>target||maxValue<target) continue;
                while(l<r){
                    //这里与之前三数之和类似，记得去重
                     int sum=nums[i]+nums[j]+nums[l]+nums[r];
                    if(sum==target){
                        res.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
                        while(l<r&&nums[l]==nums[l+1]) l++;
                        while(l<r&&nums[r]==nums[r-1]) r--;
                        l++;
                        r--;
                    }else if(sum>target) r--;
                    else l++;
                }
               
                
            }
        }
        return res;
    }
}

总结

通过上述从两数之和->三数之和->四数之和的变体，我相信你对这种给定排序数组，查询某个值的方法已经有了跟更加深刻的印象!