LEETCODE:数组(一)

本文最后更新于:6 个月前

数组是最常见最基础的数据结构了,由于它在内存中是顺序存储的,因此按下标查询的效率很高。

下面是一些我刷的数组题目的一些思路和代码。

盛最多水的容器

思路
首先想到了可以利用暴力法直接遍历出所有的容器大小,时间复杂度为$O(n^2)$

代码

public int maxArea(int[] height) {
    if (height.length == 0) {
        return 0;
    }
    int maxArea = Integer.MIN_VALUE;
    int head = 0;
    int tail;
    while (head < height.length - 1) {
        tail = height.length - 1;
        while (tail > head) {
            int minSide = Math.min(height[head], height[tail]);
            maxArea = Math.max(maxArea, (tail - head) * minSide);
            tail --;
        }
        head ++;
    }
    return maxArea;
}

提交结果
image.png
时间复杂度过于高了,该怎么优化下呢?

最初我们考虑由最外围两条线段构成的区域。现在,为了使面积最大化,我们需要考虑更长的两条线段之间的区域。如果我们试图将指向较长线段的指针向内侧移动,矩形区域的面积将受限于较短的线段而不会获得任何增加。但是,在同样的条件下,移动指向较短线段的指针尽管造成了矩形宽度的减小,但却可能会有助于面积的增大。因为移动较短线段的指针会得到一条相对较长的线段,这可以克服由宽度减小而引起的面积减小。

优化后的代码如下:

public int maxArea(int[] height) {
    if (height.length == 0) {
        return 0;
    }
    int maxArea = Integer.MIN_VALUE;
    int head = 0;
    int tail = height.length - 1;
    while (head < height.length - 1) {
        int minSide = Math.min(height[head], height[tail]);
        maxArea = Math.max(maxArea, (tail - head) * minSide);
        if (height[head] > height[tail]) {
            tail --;
        } else {
            head ++;
        }
    }
    return maxArea;
}

提交结果
image.png
瞬间快了好多,美滋滋😎

最接近的三数之和

思路
由于要计算三个数的和,如果用暴力法,会用$O(n^3)$的时间复杂度,对于这道题目会太慢了,那应该如何降低时间复杂度呢?
首先可以对数组进行排序,快速排序的时间复杂度是$O(nlogn)$,这个对速度的影响不是很大。
遍历nums数组,在使用双指针,第一个指针指向 l = i + 1 处,第二个指针指向末尾处,即 r = nums.length - 1
再根据当前三个数字的和 thisSum = nums[l] + nums[r] + nums[i] 的结果,判断与目标 target 的距离,更新当前最近距离。
然后判断 thisSumtarget 的大小关系,由于数组已经是有序的,若 thisSum > targetr--,若 thisSum < targetl++,否则说明已经找到 target ,直接返回结果即可
整个遍历过程的时间复杂度是$O(n^2)$,则总时间复杂度为 $O(nlogn) + O(n^2) = O(n^2)$

代码

public int threeSumClosest(int[] nums, int target) {
    if (nums.length < 3) {
        return target;
    }
    Arrays.sort(nums);
    int closetNum = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.length - 2; i++) {
        int l = i + 1;
        int r = nums.length - 1;
        while (l < r) {
            int thisSum = nums[l] + nums[r] + nums[i];
            if (Math.abs(thisSum - target) < Math.abs(closetNum - target)) {
                closetNum = thisSum;
            }
            if (thisSum > target) {
                r--;
            } else if (thisSum < target) {
                l++;
            } else {
                return thisSum;
            }
        }
    }
    return closetNum;
}

提交结果
image.png