[相向双指针] 167. 两数之和 II - 输入有序数组，15. 三数之和，11. 盛最多水的容器，42. 接雨水

相向双指针

该文结合灵神讲解进行编码：https://www.bilibili.com/video/BV1bP411c7oJ

相向双指针一般用于有序的数组，两个指针分别从头和尾向中间遍历，直到找到满足条件的 ans。

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

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

Solution

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int sum = 0;
        while (l < r) {
            sum = nums[l] + nums[r];
            if (sum == target) {
                return new int[]{l + 1, r + 1};
            } else if (sum < target) {
                l++;
            } else {
                r--;
            }
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

15. 三数之和

https://leetcode.cn/problems/3sum/

Solution

优化1：若最小前三个数之和已经大于零，那么指针向后移动后的三数之和只会越来越大，因此可以直接退出循环

优化2：如当前 nums[i] 与最大两个数之和小于零，说明只有 i 指针向后移动才能有机会让三数之和等于 0， 因此跳过本次循环

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums); //先排序变为有序数组
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            // 去重
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            // 优化1
            if (nums[i] + nums[i+1] + nums[i+2] > 0) {
                break;
            }
            // 优化2
            if (nums[i] + nums[n - 1] + nums[n - 2] < 0) {
                continue;
            }

            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    List<Integer> t = new ArrayList<>();
                    t.add(nums[i]);
                    t.add(nums[j]);
                    t.add(nums[k]);
                    ans.add(t);
                    j++; 
                    k--;
                    // 去重
                    while (j < k && nums[j] == nums[j-1]) {
                        j++;
                    }
                    // 去重
                    while (j < k && nums[k] == nums[k+1]) {
                        k--;
                    }
                } else if (sum > 0) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

11. 盛最多水的容器

https://leetcode.cn/problems/container-with-most-water/

Solution

class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        int l = 0, r = height.length - 1;
        while (l < r) {
            ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));
            if (height[l] > height[r]) {
                r--;
            } else {
                l++;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

42. 接雨水

https://leetcode.cn/problems/trapping-rain-water/

Solution1（前后缀分解）

把每一个槽想象为一个水桶，每个水桶能接多少水取决于左边最高的框和右边最高的框，以及桶子底的厚度。

每个水桶能存的水 == min{左边最高框, 右边最高框} - 桶子底的厚度

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];

        int ans = 0;
        left[0] = height[0];
        right[n-1] = height[n-1];
		// 左边最高框
        for (int i = 1; i < n; i++) {
            left[i] = Math.max(height[i], left[i-1]);
        }
		// 右边最高框
        for (int i = n - 2; i >= 0; i--) {  
            right[i] = Math.max(height[i], right[i+1]);
        }
        
        for (int i = 0; i < n; i++) {
            ans += Math.min(left[i], right[i]) - height[i];    
        }
        
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Solution2（相向双指针）

和 Solution1 是一样的思路，在空间上进行优化，使用左右两个指针向中心遍历。

如果左边遍历的最高的框小于右边最高的框，计算左指针指向的桶子所存的水，左指针向右移动；反之计算右指针所指向桶子所存的水，右指针向左移动。

最后左右指针会停在最高柱子的位置。

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int l = 0, r = n - 1;
        int preMax = 0, sufMax = 0;
        int ans = 0;

        while (l < r) {
            preMax = Math.max(preMax, height[l]);
            sufMax = Math.max(sufMax, height[r]);
            if (preMax < sufMax) {
                ans += preMax - height[l++];
            } else {
                ans += sufMax - height[r--];
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19