欢迎访问shiker.tech

请允许在我们的网站上展示广告

您似乎使用了广告拦截器,请关闭广告拦截器。我们的网站依靠广告获取资金。

【leetcode】刷题笔记-双指针法
(last modified Sep 18, 2022, 11:32 AM )
by
侧边栏壁纸
  • 累计撰写 176 篇文章
  • 累计创建 61 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

【leetcode】刷题笔记-双指针法

橙序员
2022-09-18 / 0 评论 / 0 点赞 / 392 阅读 / 1,626 字 / 正在检测百度是否收录... 正在检测必应是否收录...
文章摘要(AI生成)

使用两指针方法描述了两个问题及其解决方案。

第一个问题是找到最大容量的容器。 给定一个表示每个点高度的非负整数数组,任务是找到可以形成最大容量容器的两条线。 该解决方案使用两个指针,一个从数组的开头开始,另一个从数组的末尾开始。 指针相互移动,比较线的高度,并相应地更新最大容量。

第二个问题是在数组中查找总和为零的所有唯一三元组。 该解决方案还使用两指针方法。 首先对数组进行排序。 然后,选择一个固定指针(k),并且两个附加指针(i和j)向数组的中间移动。 指针检查总和为零的三元组,并记录结果。

在这两种解决方案中,都使用双指针方法来有效地遍历数组并找到所需的组合或解决方案。

盛水最多的容器

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

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

示例 1:

输入:[1,8,6,2,5,4,8,3,7]
输出:49 

示例 2:

输入:height = [1,1]
输出:1

示例 3:

输入:height = [4,3,2,1,4]
输出:16

示例 4:

输入:height = [1,2,1]
输出:2

SOLUTION:双指针法

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;
    }
}

三数之和

给你一个包含 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]
输出:[]

SOLUTION:双指针法

铺垫: 先将给定 nums 排序,复杂度为 O(NlogN)

思路: 固定 3 个指针中最左(最小)数字的指针 k,双指针 ij 分设在数组索引(k,len(nums)) 两端,通过双指针交替向中间移动,记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0i,j 组合:

  1. nums[k] > 0 时直接break跳出:因为 nums[j] >= nums[i] >= nums[k] > 0,即 3 个数字都大于 0 ,在此固定指针 k 之后不可能再找到结果了。
  2. k > 0nums[k] == nums[k - 1]时即跳过此元素nums[k]:因为已经将 nums[k - 1] 的所有组合加入到结果中,本次双指针搜索只会得到重复组合。
  3. i,j分设在数组索引(k,len(nums))两端,当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;
    }
}

合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1nums2,另有两个整数 mn ,分别表示 nums1nums2 中的元素数目。

请你 合并 nums2nums1 中,使合并后的数组同样按 非递减顺序 排列。

**注意:**最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n

示例 1:

输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。

示例 2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3:

输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

SOLUTION:双指针法

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0, p2 = 0;
        int[] sorted = new int[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
}

移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

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

SOLUTION: 双指针法

我们创建两个指针ij,第一次遍历的时候指针j用来记录当前有多少非0元素。即遍历的时候每遇到一个非0元素就将其往数组左边挪,第一次遍历完后,j指针的下标就指向了最后一个非0元素下标。
第二次遍历的时候,起始位置就从j开始到结束,将剩下的这段区域内的元素全部置为0

class Solution {
	public void moveZeroes(int[] nums) {
		if(nums==null) {
			return;
		}
		//第一次遍历的时候,j指针记录非0的个数,只要是非0的统统都赋给nums[j]
		int j = 0;
		for(int i=0;i<nums.length;++i) {
			if(nums[i]!=0) {
				nums[j++] = nums[i];
			}
		}
		//非0元素统计完了,剩下的都是0了
		//所以第二次遍历把末尾的元素都赋为0即可
		for(int i=j;i<nums.length;++i) {
			nums[i] = 0;
		}
	}
}

0

评论区