两数之和

Leetcode#165

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

如果使用穷尽，时间复杂度为$O(N^2)$。

这里注意到数组非递减顺序排列的特性，可以考虑：

  • 取第一个数与最后一个数求和，如果结果大于target，那么则需要减小（表明最后一个数加其他任何数都会大于target，可理解为使用了$O(1)$的时间获取到了$O(N)$的信息量），此时只能减小index2，对于相反情况同理只能增加index1。
  • 按照上述想法根据条件判断调整index1与index2，知道两数之和为target。
  • 此时算法时间复杂度为$O(N)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right)
        {
            if (numbers[left] + numbers[right] > target) {
                right--;
            } else if (numbers[left] + numbers[right] < target) {
                left++;
            }
            else {
                break;
            }
        }
        return new int[] {left + 1, right + 1};
    }
}

三数之和

Leetcode#15

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

由二数之和问题改编而来，这里可以考虑遍历数组中每一个数，然后再使用左右指针（需要先对数组排序）。注意点：

  • 排序复杂度：$O(N\log N)$，左右指针部分复杂度：$O(N^2)$，总体时间复杂度$O(N^2)$，空间复杂度$O(1)$（不考虑排序占用的空间）。

  • 注意到输出不能重复，所以遍历每一个数时，只需要对右侧部分使用左右指针。

  • 当前数加上后面最小的两个数还比0大，则后面任意三个数相加都大于0，直接跳出循环。
  • 当前数加上后面最大的两个数还比0小，则当前数加后面任意两个数都小于0，跳过该数。
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
class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            int j=0, k=0;
            List<List<Integer>> result = new ArrayList<>();

            // 先对数组排序
            Arrays.sort(nums);

            for (int i = 0; i < nums.length - 2; ++i) { // 遍历每一个数，重复的跳过
                int x = nums[i];
                if (i > 0 && x == nums[i - 1]) continue; // 和上一个数相同就跳过
                // 前面的数字在先前的i中已经遍历，只需要考虑当前i后面的数字
                j = i + 1;
                k = nums.length - 1;
                // 当前数加上后面最小的两个数还比0大，则后面任意三个数相加都大于0，直接跳出循环
                if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
                // 当前数加上后面最大的两个数还比0小，则当前数加后面任意两个数都小于0，跳过该数
                if (nums[i] + nums[k - 1] + nums[k] < 0) continue;
                while (j < k) {
                    // 边界调整逻辑
                    if (x + nums[j] + nums[k] > 0) {
                        --k;
                    } else if (x + nums[j] + nums[k] < 0) {
                        ++j;
                    }
                    else
                    {
                        result.add(new ArrayList<>(Arrays.asList(x, nums[j], nums[k])));
                        // 下面是防止结果重复的逻辑
                        ++j;
                        while (j < k && nums[j] == nums[j - 1]) ++j; // 注意j<k的条件
                        --k;
                        while (j < k && nums[k] == nums[k + 1]) --k; // 注意j<k的条件
                    }
                }
            }
            return result;
        }
    }

盛最多水的容器

Leetcode#11

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]

输出：49

解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

还是使用左右指针，考虑：

对于某一种情况，分析更高一边的指针向内移动时，如果遇到了更长的边，水高度不变、宽度变小，整体容量必然减小；如果遇到更短的边，高、宽都减小，容量也减小。因此，向内移动长边的指针必然不会得到更大的容量，所以只能移动短边的指针，并与当前的最大容量进行比较。算法时间复杂度为$O(N)$。

进一步优化，移动短边指针时，之后必须找到更高的边才存在容量变大的可能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
        public int maxArea(int[] height) {
            int left = 0, right = height.length - 1, area = 0, cur_h = 0;
            while (left < right) {
                area = Math.max(area, (right - left) * Math.min(height[left], height[right]));
                if (height[left] > height[right]) {
                    cur_h = height[right];
                    right--;
                    while (left < right && height[right] < cur_h) right--;	// 向内寻找更高的边
                }
                else {
                    cur_h = height[left];
                    left++;
                    while (left < right && height[left] < cur_h) left++;	// 向内寻找更高的边
                }
            }
            return area;
        }
    }

接雨水

LeetCode#42

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

对于每一个单位宽度的柱子，可将其两侧视为容器的两边，这个容器两边的高度分别对应于这一侧柱子的最大高度，而内部水的体积取决于两侧最大高度中的最小高度。因此，可以设置左右指针，每次移动高度较小一侧的指针（因为此时该处柱子内的高度只取决于较低的一侧）。时间复杂度为$O(N)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int trap(int[] height) {
        int area = 0;
        int pre_max = 0, suf_max = 0;
        int left = 0, right = height.length - 1;
        while (left < right) {
            pre_max = Math.max(pre_max, height[left]);
            suf_max = Math.max(suf_max, height[right]);
            if (pre_max > suf_max) {
                area += suf_max - height[right];
                right--;
            }
            else {
                area += pre_max - height[left];
                left++;
            }
        }
        return area;
    }
}