双指针方案-有序矩阵

适用于有序矩阵(数组也是矩阵),相比其他算法目的是减少搜索空间,但是有前提条件,有序。关键思想:固定参数,比较,舍弃不合适的搜索空间。

例子1、给定一个已按照升序排列的有序数组,找到两个数使得它们相加之和等于目标数(不可以重复使用同一个数),返回两个数的下标值 i 和 j,要求 i < j。

假设每个输入有且仅有一个答案。

示例:

输入:numbers = [2, 7, 11, 15], target = 9

输出:[0, 1]

(注意:这里和原题略有不同,下标改为从 0 开始,更自然。)

public int[] twoSum(int[] nums, int target) {

    int i = 0;

    int j = nums.length - 1;

    while (i < j) {

        int sum = nums[i] + nums[j];

        if (sum < target) {

            i++;

        } else if (sum > target) {

            j--;

        } else {

            return new int[]{i, j};

        }

    }

    return new int[]{-1, -1};

}

举一反三:二维矩阵搜索

例题:LeetCode 240 - Search a 2D Matrix II[2](Medium)

一个  的矩阵 matrix 有如下特点:

每行的元素从左到右升序排列

每列的元素从上到下升序排列

写一个高效的算法在矩阵中搜索目标值 target。

本期题解:LeetCode 11 - Container With Most Water[1](Medium)

给定  个非负整数 ,每个数代表坐标中的一个点  。在坐标内画  条竖直线,竖直线  的两个端点分别为  和 。找出其中的两条线,使得它们与  轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且  的值至少为 2。

题目示例

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

public int maxArea(int[] height) {

    int res = 0;

    int i = 0;

    int j = height.length - 1;

    while (i < j) {

        int area = (j - i) * Math.min(height[i], height[j]);

        res = Math.max(res, area);

        if (height[i] < height[j]) {

            i++;

        } else {

            j--;

        }

    }

    return res;

}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 题目详细说明请自行到题库 - 力扣 (LeetCode)搜寻题号 1. 两数和 利用数组的有序,使用两个指针,一个...
    明年决赛小牛打雄鹿阅读 457评论 0 0
  • 目录 1 左神部分集锦 2 Leetcode前150题 3 牛客网剑指offer 4 JavaG 5 题目中的...
    小小千千阅读 1,063评论 0 0
  • 最近在准备面试,发现自己真的菜的不行,就计划接下来的时间把 leetcode 上面刷的 中等题 和 每日一题做个简...
    毒死预言家的女巫阅读 687评论 0 3
  • 七.数组 1.给定一个整数数组 nums和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返...
    寒江_d764阅读 319评论 0 0
  • 算法口试也就是用自然语言描述算法,脑海中要有一个流程图。 【目录】考点一:循环考点二:递归考点三:排序考点四:查找...
    三金姐姐阅读 707评论 -1 2