力扣刷题：Array之双指针专项

力扣刷题：Array之双指针专项

前言

难度从易到难，应该顺序阅读，代码都是实际跑过的，都可以运行。

11.盛最多水的容器

难度：中等
标签：双指针

给你n个非负整数a1，a2，...，an，每个数代表坐标中的一个点(i, ai)。在坐标内画n条垂直线，垂直线i的两个端点分别为(i, ai)和(i, 0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

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

提示：

$n = height.length$
$2 \leq n \leq 10^5$
$0 \leq height[i] \leq 10^4$

思路：双指针，一个左值针、一个右指针。因为我们要求容器最大值，容易想到左右指针应当离得足够远。我们起始让左值针指向最左端，右指针指向最右端。

当左值针低于右指针时（左值针值小于右指针值，形象地说），使左值针向右移动
否则，右指针向左移动

接下来解释为什么

左右指针均是向中心移动，所以底（容器最大值=底x高）是不断减小的。
面积取决于较小的那一个，而另一个不管多高都影响不了我们所求的面积。
所以如果我们移动较大的那一个，那不管他接下来的值是更大还是更小，我们所求的面积都会减小。因为底减小，高只可能更小而不可能更大。
我们应该移动较小的那一个，因为我们确定底会不断减小。但我们移动较小的那一个可能使高增加，从而有可能使整个面积增加。
于是我们不断重复上述移动左右指针的过程，直到左右指针指向同一个元素。

题解：

时间复杂度： $O(n)$

class Solution {
public:
    int maxArea(vector<int>& height) {
        int start = 0,end = height.size() - 1;
        int result = 0;
        while(start < end){
            int area = min(height[start], height[end]) * (end - start);
            if(area > result)
                result = area;
            if(height[start] > height[end])
                --end;
            else   
                ++start;
        }
        return result;
    }
};

15.三数之和

难度：中等
标签：双指针

给你一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a + b + c = 0？请你找出所有和为0且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

$0 \leq nums.length \leq 3000$
$-10^5 \leq nums[i] \leq 10^5$

思路：为了确保不重复，先将数组排序

首先第一层循环取数a，需要注意的是数a递增时，应该跳过上一轮相同的数，即每次循环的数不同。
然后第二层循环取数b，b的起始值是a+1。递增同a一样，跳过相同的数。
然后我们设置数c为数组尾，因为数组是排序的，a和b位于数组头，都是较小的值。数组尾有更大的机会使和为0。
当a + b + c > 0时，c过大，此时递减c的值。
当a + b + c < 0时，b过小，递增b。
当a + b + c = 0时，即为答案。

题解：

时间复杂度： $O(n^2)$

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());//排序
        vector<vector<int>> ans;
        if(nums.size() < 3 || nums[0] > 0) return ans;//不可能有答案的情况

        for (int first = 0; first < n; ++first) {
            //需要和上一轮的数不同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            //c初始为最右端
            int third = n - 1;

            for (int second = first + 1; second < third; ++second) {
                //需要和上一轮的数不同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                //如果c过大，递减c
                while (second < third && nums[first]+nums[second]+nums[third] > 0) {
                    --third;
                }
                if (nums[first]+nums[second]+nums[third] == 0) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

16.最接近的三数之和

难度：中等
标签：双指针

给你一个长度为n的整数数组nums和一个目标值target。请你从nums中选出三个整数，使它们的和与target最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是2(-1 + 2 + 1 = 2)

示例 2：

输入：nums = [0,0,0], target = 1
输出：0

提示：

$3 \leq nums.length \leq 1000$
$-1000 \leq nums[i] \leq 1000$
$-10^4 \leq target \leq 10^4$

思路：与三数之和类似，先将数组排序

首先第一层循环取数a，需要注意的是数a递增时，应该跳过上一轮相同的数，即每次循环的数不同。
然后第二层循环取数b，b的起始值是a+1。递增同a一样，跳过相同的数。
然后我们设置数c为数组尾，我们为了让a + b + c接近target有以下移动规则。
当a + b + c - target < 0时，数不够大，递增b。
当a + b + c - target > 0时，数不够小，递减c。
当a + b + c - target == 0时，没有比0更小的距离了，此时可以直接输出答案。

题解：

时间复杂度：O(n^2)

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        if(n== 3 || target < nums[0]+nums[1]+nums[2]) 
			return nums[0]+nums[1]+nums[2];
        if(target > nums[n-1]+nums[n-2]+nums[n-3])
            return nums[n-1]+nums[n-2]+nums[n-3];

        int difference = 0x7fffffff;
        int anwser = 0;
        for(int a = 0; a < n-2; ++a) {
            if(a > 0 && nums[a] == nums[a-1]) continue;
            int b = a + 1, c = n - 1;

            while(b < c){
                int absn = abs(nums[a]+nums[b]+nums[c]-target);
                if(absn < difference){
                    difference = absn;
                    anwser = nums[a]+nums[b]+nums[c];
                    if(anwser == target) return anwser;
                }
                if(nums[a]+nums[b]+nums[c]-target < 0){
                    do
                        ++b;
                    while(b < c && b > a+1 && nums[b] == nums[b-1]);
                }else if(nums[a]+nums[b]+nums[c]-target > 0){
                    do
                        --c;
                    while(b < c && c < n-2 && nums[c] == nums[c+1]);
                }else{
                    anwser = nums[a]+nums[b]+nums[c];
                    return anwser;
                }
            }
        }
        return anwser;
    }
};

18.四数之和

难度：中等
标签：双指针

给你一个由n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

$1 \leq nums.length \leq 200$
$-10^9 \leq nums[i] \leq 10^9$
$-10^9 \leq target \leq 10^9$

这里有个细节，虽然数组和target都不会超过int范围，但在计算四数和时，可能超过。
例如输入：nums = [200000000, 200000000, 200000000, 200000000], target = 0

思路：这里讲的比较简略，需要先看懂三数之和。
与三数之和类似，先将数组排序，只在最内层的c和d采用双指针，外层元素仍然是逐个遍历。但要注意跳过相同的元素。

虽然时间复杂度仍然为 $O(n^3)$ ，但仍可以做一些额外的剪枝优化，达到一个常数级的优化效果（实测有5-6倍左右的提升）。
我们考虑以下几种特殊情况：
b所在的循环：

nums[a] + nums[a+1] + nums[a+2] + nums[a+3] > target，此时再将a右移，四数和增大，不可能使等式相等。所以此时可以直接返回结果了。
nums[a] + nums[d] + nums[d-1] + nums[d-2]) < target，此时为b、c、d可能达到的最大值，仍然小于target，所以没有必要再遍历b、c、d了，直接增大a。

c和d所在的循环：

nums[a] + nums[b] + nums[b+1] + nums[b+2]) > target，此时为c、d可能达到的最小值，仍然大于target，所以此时没必要再遍历c和d了。但不能返回结果，a增大b减小仍有可能使等式成立。这里应该直接跳到a所在的循环，增加a，重置b（b=a+1，减小b）。
nums[a] + nums[b] + nums[d] + nums[d-1]) < target，此时为c、d可能达到的最大值，但仍小于target，所以没必要再遍历c和d了，直接增大b的值。

题解：

时间复杂度： $O(n^3)$

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> result;
        if(n < 4) return result;
        sort(nums.begin(), nums.end());
        for(int a = 0; a < n-3; ++a){
			//避免重复遍历a
            if(a > 0 && nums[a-1] == nums[a]) continue;
            int b = a + 1;
            for(;b < n-2; ++b){
				//避免重复遍历b
                if(b > a+1 && nums[b] == nums[b-1]) continue;
                int c = b + 1;
                int d = nums.size() - 1;
				//特殊情况1
                if(((long int)nums[a] + nums[a+1] + nums[a+2] + nums[a+3]) > target)
                    return result;
				//特殊情况2
                else if(((long int)nums[a] + nums[d] + nums[d-1] + nums[d-2]) < target)
                    break;
                while(c < d){
                    long int sum = (long int)nums[a] + nums[b] + nums[c] + nums[d];
					//特殊情况3
                    if(((long int)nums[a] + nums[b] + nums[b+1] + nums[b+2]) > target)
                        break;
					//特殊情况4
                    else if(((long int)nums[a] + nums[b] + nums[d] + nums[d-1]) < target){
                        break;
                    }
                    if(sum == target){
                        result.push_back({nums[a], nums[b], nums[c], nums[d]});
                    }else if(sum > target){
						//避免重复遍历d
                        do
                            --d;
                        while(c < d && d < nums.size()-2 && nums[d] == nums[d+1]);
                        continue;
                    }
					//避免重复遍历c
                    do
                        ++c;
                    while(c < d && c > b+1 && nums[c] == nums[c-1]);
                }
            }
        }
        return result;
    }
};

文章作者: Yuan.

文章链接: /archives/leetcodearraydoubleptr

微信扫一扫

评论 | 0条评论