自学内容网 自学内容网

【每日力扣】15. 三数之和与11. 盛最多水的容器

在这里插入图片描述

🔥 个人主页: 黑洞晓威
😀你不必等到非常厉害,才敢开始,你需要开始,才会变的非常厉害

15. 三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

解题思路

先将 nums 排序,时间复杂度为 O(NlogN)O(NlogN)O(Nlog**N)。

固定 333 个指针中最左(最小)元素的指针 k,双指针 ij 分设在数组索引 (k,len(nums))(k, len(nums))(k,len(num**s)) 两端。

双指针 iii , jjj 交替向中间移动,记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0i,j 组合:

  1. nums[k] > 0 时直接break跳出:因为 nums[j] >= nums[i] >= nums[k] > 0,即 333 个元素都大于 000 ,在此固定指针 k 之后不可能再找到结果了。

  2. k > 0nums[k] == nums[k - 1]时即跳过此元素nums[k]:因为已经将 nums[k - 1] 的所有组合加入到结果中,本次双指针搜索只会得到重复组合。

  3. i,j 分设在数组索引(k,len(nums))(k, len(nums))(k,len(num**s))两端,当i < j时循环计算s = nums[k] + nums[i] + nums[j]

    ,并按照以下规则执行双指针移动:

    • s < 0时,i += 1并跳过所有重复的nums[i]
    • s > 0时,j -= 1并跳过所有重复的nums[j]
    • s == 0时,记录组合[k, i, j]res,执行i += 1j -= 1并跳过所有重复的nums[i]nums[j],防止记录到重复组合。

代码实现

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int k = 0; k < nums.length - 2; k++){
            if(nums[k] > 0) break;
            if(k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1, j = nums.length - 1;
            while(i < j){
                int sum = nums[k] + nums[i] + nums[j];
                if(sum < 0){
                    while(i < j && nums[i] == nums[++i]);
                } else if (sum > 0) {
                    while(i < j && nums[j] == nums[--j]);
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
}

11. 盛最多水的容器

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

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

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

**说明:**你不能倾斜容器。

image-20240417134953348

解题思路

在每个状态下,无论长板或短板向中间收窄一格,都会导致水槽 底边宽度 −1-1−1 变短:

  • 若向内 移动短板 ,水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 可能变大,因此下个水槽的面积 可能增大
  • 若向内 移动长板 ,水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 不变或变小,因此下个水槽的面积 一定变小

因此,初始化双指针分列水槽左右两端,循环每轮将短板向内移动一格,并更新面积最大值,直到两指针相遇时跳出;即可获得最大面积。

  1. 初始化: 双指针 iii , jjj 分列水槽左右两端;

  2. 循环收窄:

    直至双指针相遇时跳出;

    1. 更新面积最大值 resresres
    2. 选定两板高度中的短板,向中间收窄一格;
  3. 返回值: 返回面积最大值 resresres 即可;

代码实现

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while(i < j) {
            res = height[i] < height[j] ? 
                Math.max(res, (j - i) * height[i++]): 
                Math.max(res, (j - i) * height[j--]); 
        }
        return res;
    }
}

原文地址:https://blog.csdn.net/m0_69383623/article/details/137870439

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!