LeetCode 数组:1.两数之和 11. 盛最多水的容器

1.两数之和

LeetCode 数组:1.两数之和 11. 盛最多水的容器

 思路:

都会想到的肯定是两重循环,但这会导致一个n平方的时间复杂度。有一个问题是,我在看浙大数据结构课中,其中提到如果见到n平方,要想办法做成nlogn,所以思路往那边想去了。所以,什么情况下能尝试吧n平方优化成nlogn呢?

没想到的是,LeetCode给的官方解法是hashmap的方式,一次遍历,判断是否有target-nums[i]交给哈希表做就好。这样的空间复杂度是On,时间复杂度是On。还有就是,可能在map里通过value找key麻烦一些,所以key设置成了nums[i],value设置成了i

java中的hashmap还不太熟,需要进一步熟悉

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

11. 盛最多水的容器

LeetCode 数组:1.两数之和 11. 盛最多水的容器

 思路:最容易想到的思路仍然是两次遍历(事实上如果不动动脑筋,每一个数组题都是两次遍历哈哈)。但是我们直觉肯定能感觉到,在两次遍历中出现了大量无效的遍历,就是那些明明相比前一种情况面积缩水了的反而被遍历到了。

问题是,在改变高度的同时宽度也在变化。能否构造出一种情况,能让我们发现明显的面积缩水从而排除一些选择呢?关键要保证宽度不能增加,只能不变或缩小。

想到这里,就不难想到,把初始情况设置成在两侧。现在的遍历变成了两侧向中间挪,我们发现,每次移动都不能动两侧中较大的那一侧,因为会导致宽度缩减的同时,高度不变或者缩减(短端只可能更短)。想象一个分叉的选择树,我们每次选择都砍掉了一个分支。

无论我们怎么移动右指针,得到的容器的容量都小于移动前容器的容量。也就是说,这个左指针对应的数不会作为容器的边界了,那么我们就可以丢弃这个位置,将左指针向右移动一个位置,此时新的左指针于原先的右指针之间的左右位置,才可能会作为容器的边界。
 

但是这样解释感觉还是有疑惑的,从两边向中间移感觉非常不直观,老是感觉不能覆盖所有的选择。这时候看到了一个非常优秀的解释:

https://leetcode-cn.com/problems/container-with-most-water/solution/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu/

LeetCode 数组:1.两数之和 11. 盛最多水的容器

 不得不说这样看相当直观每次移动边界就能消掉一行或者一列的可能,原本明显是n平方的遍历变为了n复杂度的。

所以本题的思想在于缩减搜索空间

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