数组-双指针之左右指针（这期长，忍一下）

前言

兄弟们，上篇文章讲了双指针的快慢指针，双指针是数组类算法题中最重要的一个分支之一。这篇文章讲双指针技巧的左右指针技巧。文章很长，几乎涵盖了所有的左右指针技巧，希望大家能耐心看完。另外，数组有下图这些知识点与技巧。


思路

通过条件控制左右指针往中间移动，注意处理好细节，左右指针移动模板如下。
l = 0, r = nums.length - 1;
if (res > target) {
    r--;
} else if (res < target) {
    l++;
}

两数之和 II - 输入有序数组

leetcode第167题


解题思路
左右指针。若两数之和大于目标数，右指针-1。若小于目标数，左指针+1。

复杂度分析
时间复杂度：O(n)，n是数组的长度。
空间复杂度：O(1)。

代码

class Solution {
    public int[] twoSum(int[] numbers, int target) {
      for (int left = 0, right = numbers.length - 1; left < right; ) {
         if (numbers[left] + numbers[right] > target) {
            right--;
         } else if (numbers[left] + numbers[right] < target){
            left++;
         } else {
            return new int[] {left + 1, right + 1};
         }
      }
      return null;
    }
}

最长回文子串

leetcode第5题

解题思路
左右指针。从数组i = 0开始，以此选定中心数字，然后围绕中心数字，计算出最长的回文字串。但选定中心数字i后，有两种计算回文的方式。
方式一：将i - 1与i + 1比较，i - 2与i + 2比较，以此类推。即回文子串的长度为奇数。
方式二：将i - 1与i比较，i - 2与i + 1比较，以此类推，即回文子串的长度为偶数。
需要注意，上文中给的左右指针模板是从左右两边往中间移动，而该题的思路，是左右指针从中心数字往左右两边移动。

复杂度分析
时间复杂度：O(n2)，n 是字符串的长度。字符串最多有n个中心数字，中心数字最多会向外扩展n / 2次。
空间复杂度：O(1)。

代码

class Solution {
   public String longestPalindrome(String s) {
      String max = "", sub = "";
      for (int mid = 0; mid < s.length(); mid++) {
         //回文子串的长度为奇数时
         sub = maxPalindromeOfMid(s, mid - 1, mid + 1);
         max = max.length() > sub.length() ? max : sub;
         //回文子串的长度为偶数时
         sub = maxPalindromeOfMid(s, mid - 1, mid);
         max = max.length() > sub.length() ? max : sub;
      }
      return max;
   }

   private String maxPalindromeOfMid(String s, int l, int r) {
      //计算回文的数量
      while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
         l--;
         r++;
      }
      return s.substring(l + 1, r);
   }
}

优势洗牌

leetcode第870题

解题思路

使用田忌赛马的策略，假设nums1与nums2的长度都是3。每个元素从小到大依次称为下等马，中等马，上等马。

用nums1的上等马与nums2的上等马比较，如果有优势（即num1中最大的数>nums2中最大的数），则使用nums1的上等马，如果没有优势，则使用nums1的剩余的下等马（即nums1中未使用过的数中最小的那个）。

这里可能读者会有疑问：如果nums1的中等马对nums2的上马也有优势。是否需要用nums1的中等马对战nums2的上等马，达到节约战力的作用呢？

答案是没有必要。如果nums1的中等马对nums2的上等马有优势，则nums1的中等马对nums2的中等马也会有优势的。

转换为代码：使用左右指针，先将nums1，nums2降序排列，然后左指针指向num1中最小的数，右指针指向num1中最大的数。

依此从大到小拿出num2中的每个数。如果nums2中拿出的数比nums1的最大数小，则就使用nums1的最大数，否则使用nums1最小数。

复杂度分析
时间复杂度：O(n)，数组nums2长度。
空间复杂度：O(n)。

代码

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
      Arrays.sort(nums1);
      //o[0]是nums2的值，0[1]是nums2的下标
      PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);
      for (int i = 0; i < nums2.length; i++) {
         queue.offer(new int[] {nums2[i], i});
      }
      int[] res = new int[nums1.length];
      int l = 0, r = res.length - 1;
      while (!queue.isEmpty()) {
         int[] item = queue.poll();
         int val = item[0], idx = item[1];
         //比得过就比
         if (nums1[r] > val) {
            res[idx] = nums1[r];
            r--;
         } else {
            //比不过就用最小的数去混
            res[idx] = nums1[l];
            l++;
         }
      }
      return res;
    }
}

小于 K 的两数之和

leetcode第1099题

解题思路

  1. 将nums升序排序。
  2. 初始状态令左指针l = 0，右指针r = nums.length - 1。
  3. 当nums[l] + nums[r] >= k时，则左移右指针。
  4. 当nums[l] + nums[r] < k时，则右移左指针，并更新结果sum。
  5. 重复3-4步，直到l不再小于r为止。

复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。

代码

class Solution {
    public int twoSumLessThanK(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1, sum = -1;
        while (l < r) {
            int res = nums[l] + nums[r];
            if (res < k) {
                sum = Math.max(sum, res);
                l++;
            } else {
                r--;
            }
        }
        return sum;
    }
}

较小的三数之和

leetcode第259题

解题思路
使用左右指针技巧，例如nums = [0, 1, 2, 3, 4]。

  1. 将nums数组升序排序。
  2. 外层循环，将i从0开始，直到i不再小于nums.length - 2。为什么是nums.length - 2，下文会讲。
  3. 在数组中i的右侧位置，嵌套内层循环，内层循环使用左右指针（因为i的右侧有左右指针，至少会占两个位置，所以i最4. 多到nums.length - 3），令l = i + 1，r = nums.length - 1。
  4. 当nums[i] + nums[l] + nums[r] >= target时，则将r指针左移动一位。
  5. 当nums[i] + nums[l] + nums[r] < target时，r - l的值就是在当前l的取值下满足题意的三元组的个数。再将l指针右移动一位。
  6. 重复4.5步，直到l不再小于r为止。
  7. i右移动一位，重复3-6步，直到i不再小于nums.length - 2为止。

复杂度分析
时间复杂度：O(n2)。内层的双指针循环复杂度为O(n)，再加上外层循环，所以复杂度为O(n2)。
空间复杂度：O(1)。

代码

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
      Arrays.sort(nums);
      int count = 0;
      for (int i = 0; i < nums.length - 2; i++) {
         int l = i + 1, r = nums.length - 1;
         while (l < r) {
            if (nums[i] + nums[l] + nums[r] < target) {
               count += r - l;
               l++;
            } else {
               r--;
            }
         }
      }
      return count;
    }
}

最接近的三数之和

leetcode第16题

解题思路
使用左右指针技巧，与《259.较小的三数之和》类似。例如nums = [0, 1, 2, 3, 4]。

  1. 将nums数组升序排序。
  2. 外层循环，将i从0开始遍历，直到i不再小于nums.length - 2。
  3. 在数组中i的右侧位置，嵌套内层循环，内层循环使用左右指针（因为i的右侧有左右指针，至少会占两个位置，所以i最多到nums.length - 3），令左指针l = i + 1，右指针r = nums.length - 1。
  4. 计算res = nums[i] + nums[l] + nums[r]。若res - target的绝对值比上次res - target的绝对值小，即这次的三个数和更接近target，则记录下当前res。
  5. 当res > target时，则将r指针左移动一位。
  6. 当res < target时，则再将l指针右移动一位。
  7. 当res = target时，直接返回res。
  8. 重复4-7步，直到l不再小于r为止。
  9. i右移动一位，重复3-8步，直到i不再小于nums.length - 2为止。

复杂度分析
时间复杂度：O(n2)。内层的双指针循环复杂度为O(n)，再加上外层循环，所以复杂度为O(n2)。
空间复杂度：O(1)。

代码

class Solution {
    public int twoSumLessThanK(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1, sum = -1;
        while (l < r) {
            int res = nums[l] + nums[r];
            if (res < k) {
                sum = Math.max(sum, res);
                l++;
            } else {
                r--;
            }
        }
        return sum;
    }
}

三数之和

leetcode第15题


解题思路
想要求三数和，首先用左右指针求两数和，注意结果集记得去重。
拓展：若要求n数和，则先求n - 1数和。若想求n - 1数和，则先求n - 2数和，依此类推，一开始先用左右指针求两数和。

复杂度分析
时间复杂度：O(n2)，左右指针计算两数和的复杂度是O(n)，再加上左右指针的外层循环，也就是确定第三个数的循环的复杂度时O(n)，因此为O(n2)。
空间复杂度：O(n3)。需要中间变量存储递归返回的结果即排列中的C_n^3。

代码
该代码是n数和的模板代码，《18.四数之和》可以用该模板。

class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            return nSum(nums, 3, 0, 0);
        }

        private List<List<Integer>> nSum(int[] nums, int n, int start, int sum) {
            int len = nums.length;
            if (len < 2 || n > len) {
                return new ArrayList<>();
            }
            if (n == 2) {
                return sumTwo(nums, start, sum);
            }
            int lastNum = Integer.MIN_VALUE;
            List<List<Integer>> list = new ArrayList<>();
            for (int i = start; i < len - 2; i++) {
                //i右移后值还是与右移前相等，则继续右移
                if (lastNum == nums[i]) {
                    continue;
                }
                lastNum = nums[i];
                //和为sum - nums[i]的n - 1数和的数组下标
                List<List<Integer>> res = nSum(nums, n - 1, i + 1, sum - nums[i]);
                for (List<Integer> item : res) {
                    item.add(nums[i]);
                    //添加到结果集
                    list.add(item);
                }
            }
            return list;
        }

        private List<List<Integer>> sumTwo(int[] nums, int start, int sum) {
            List<List<Integer>> list = new ArrayList<>();
            int l = start, r = nums.length - 1;
            while (l < r) {
                int twoSum = nums[l] + nums[r];
                int left = nums[l], right = nums[r];
                //两数和小于目标值，左指针右移
                if (twoSum < sum) {
                    //右移后的值与右移前的值相等，且左指针比右指针小，则左指针继续右移
                    while (l < r && left == nums[l]) {
                        l++;
                    }
                }
                //两数和大于目标值，左指针右移
                else if (twoSum > sum) {
                    //右移后的值与右移前的值相等，且左指针比右指针小，则右指针继续左移
                    while (l < r && right == nums[r]) {
                        r--;
                    }
                }
                //两数和等于目标值
                else {
                    list.add(new ArrayList<>(Arrays.asList(nums[l], nums[r])));
                     //右移后的值与右移前的值相等，且左指针比右指针小，则左指针继续右移
                    while (l < r && left == nums[l]) {
                        l++;
                    }
                    //右移后的值与右移前的值相等，且左指针比右指针小，则右指针继续左移
                    while (l < r && right == nums[r]) {
                        r--;
                    }
                }
            }
            return list;
        }
    }

四数之和

leetcode第18题

解题思路
想要求三数和，首先用左右指针求两数和，注意结果集记得去重。
拓展：若要求n数和，则先求n - 1数和。若想求n - 1数和，则先求n - 2数和，依此类推，一开始先用左右指针求两数和。
参考《三数之和》的模板代码

复杂度分析
时间复杂度：O(n3)，左右指针计算两数和的复杂度是O(n),除了左右指针外，剩余两个数，每个数有一个循环，分别都为O(n)，因此为O(n3)。
空间复杂度：O(n4)。需要中间变量存储递归返回的结果即排列中的Cn4。

代码
套用n数和的模板。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return nSum(nums, 4, 0, target);
    }

    private List<List<Integer>> nSum(int[] nums, int n, int start, int sum) {
        int len = nums.length;
        if (len < 2 || n > len) {
            return new ArrayList<>();
        }
        if (n == 2) {
            return sumTwo(nums, start, sum);
        }
        int lastNum = Integer.MIN_VALUE;
        List<List<Integer>> list = new ArrayList<>();
        for (int i = start; i < len - 2; i++) {
            //i右移后值还是与右移前相等，则继续右移
            if (lastNum == nums[i]) {
                continue;
            }
            lastNum = nums[i];
            //和为sum - nums[i]的n - 1数和的数组下标
            List<List<Integer>> res = nSum(nums, n - 1, i + 1, sum - nums[i]);
            for (List<Integer> item : res) {
                item.add(nums[i]);
                //添加到结果集
                list.add(item);
            }
        }
        return list;
    }
    
    private List<List<Integer>> sumTwo(int[] nums, int start, int sum) {
        List<List<Integer>> list = new ArrayList<>();
        int l = start, r = nums.length - 1;
        while (l < r) {
            int twoSum = nums[l] + nums[r];
            int left = nums[l], right = nums[r];
            //两数和小于目标值，左指针右移
            if (twoSum < sum) {
                //右移后的值与右移前的值相等，且左指针比右指针小，则左指针继续右移
                while (l < r && left == nums[l]) {
                    l++;
                }
            }
            //两数和大于目标值，左指针右移
            else if (twoSum > sum) {
                //右移后的值与右移前的值相等，且左指针比右指针小，则右指针继续左移
                while (l < r && right == nums[r]) {
                    r--;
                }
            }
            //两数和等于目标值
            else {
                list.add(new ArrayList<>(Arrays.asList(nums[l], nums[r])));
                 //右移后的值与右移前的值相等，且左指针比右指针小，则左指针继续右移
                while (l < r && left == nums[l]) {
                    l++;
                }
                //右移后的值与右移前的值相等，且左指针比右指针小，则右指针继续左移
                while (l < r && right == nums[r]) {
                    r--;
                }
            }
        }
        return list;
    }
}

盛最多水的容器

leetcode第11题

解题思路
该题仍然采用左右指针思路，每次向中间移动左右两块柱子中较矮的那一根，并记录容纳水的最大值。
具体步骤：

  1. 双指针l , r指向水槽的两端。
  2. 哪个指针指向的元素小，就往中间移动，相同时任意往中间移动一个指针并更新容纳水的最大值。
  3. 直到l不再小于r位置，并返回容纳水的最大值。
    上述思路的正确性证明：
    令左指针=l，右指针=r，左右指针的距离为w，则面积S(l, r) = min(h[l], h[r]) * w。

当h[l] < h[r]时，l++。会丢失掉S(l, l + 1), S(l, l + 2), ..., S(l, r - 1)这几种可能， 统称为S(l, r') = min(h[l], h[r']) * w'。

又因为h[l] < h[r]，所以h[l]<h[r']时min(h[l], h[r']) = h(l)，h[l]>h[r']时min(h[l], h[r'])=h[r'].所以min(h[l], h[r']) <=min(h[l], h[r])。

又因为w' < w。所以min(h[l], h[r']) * w' < min(h[l], h[r]) * w，所以 S(l,r') < S(l, r)。

所以左指针右移后丢掉的几种可能的面积中，都比右移前的面积小。

同理可得出h[l] > h[r]时，r--，丢掉的几种可能的面积中，都比移动前更小。

进一步得出：h[l] = h[r]时，可以任意移动左指针或者右指针。

复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。

代码

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1, max = Math.min(height[l], height[r]) * (r - l);
        while (l < r) {
            if (height[l] <= height[r]) {
                l++;
            } else {
                r--;
            }
            int area = Math.min(height[l], height[r]) * (r - l);
            max = Math.max(area, max);
        }
        return max;
    }
}

接雨水

leetcode第42题

解题思路
采用左右指针思路，该题非常巧妙简洁：

移动左指针时，左指针最新指向的柱子上方能接的水，为该柱子左指针右移时扫过部分（除开最新指向的那一根柱子）中最高的那根A，与右指针左移扫过部分中最高的那根B中较矮的那一根，与当前柱子的差值。

移动右指针时，右指针最新指向的柱子上方能接的水，为左指针右移扫过部分中最高的那根A，与柱子右指针左移扫过部分中最高的那根B（除开右指针最新指向的那个柱子）中较矮的那一根，与当前柱子的差值。

具体步骤：

  1. 双指针l , r分别指向0，height.length - 1。左指针扫过lMax=heigth[0]，右边最高的柱子为rMax = heigth[height.length - 1]。
  2. 如果l指向的柱子更低，即height[l] < height[r]。右移左指针，即l++。此时l指向的柱子的左边最高的柱子的高度就是lMax，l指向的柱子的右边，且r指针扫过的柱子中，最高的柱子的高度就是rMax。当前柱子上方能接的水就是ans = min(lMax, rMax) - 当前柱子高度。注意若ans <0，该柱子上方就不能接水。此时比较lMax与l所指向的柱子的高度，谁高就将谁赋值给lMax。
  3. 如果r指向的柱子更低或者二者相同，根据第2步来镜像处理。
  4. 重复2-3步，直到l不再小于r为止，统计每根柱子上方能接的雨水。

复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)。

代码

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, sum = 0, lMax = height[l], rMax = height[r];
        while (l < r) {
            int minHeight = Math.min(lMax, rMax);
            if (height[l] < height[r]) {
                l++;
                sum += Math.max(0, minHeight - height[l]);
                lMax = Math.max(lMax, height[l]);
            } else {
                r--;
                sum += Math.max(0, minHeight - height[r]);
                rMax = Math.max(rMax, height[r]);
            }
        }
        return sum;
    }
}

结尾

恭喜你已经掌握了双指针之左右指针，下篇算法文章讲双指针的滑动窗口。
感谢各位人才的点赞、收藏和评论，干货文章持续更新中，下篇文章再见！

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,718评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,683评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,207评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,755评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,862评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,050评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,136评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,882评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,330评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,651评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,789评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,477评论 4赞 333
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,135评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,864评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,099评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,598评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,697评论 2赞 351

推荐阅读更多精彩内容