技巧题目总结

Leetcode (opens new window) 的刷题过程中,我们总会遇到这样一类题:

  1. 没有思路下手
  2. 暴力方法破解(看了题目分类一头雾水)
  3. 一看题解,直呼OMG,秒

这不禁让我想起上初高中的时光,要想取得高(满)分,这就要求我们看见题目,就能找出题眼之所在。

遂有此文,以供参考。


977. 有序数组的平方 - E (opens new window)

这道题就很有意思啦.对于有经验的同学,有序数组可以算是一个题眼,毕竟可以考虑用二分查找。不过也仅限于此,

如果你不能有更深入的思考并得到最大值只可能出现在两端(题眼)。Game Over.

最大值只可能出现在数组的两端 ----> 双指针。

class Solution {
    public int[] sortedSquares(int[] nums) {
        if(nums == null || nums.length == 0){
            return nums;
        }

        int start = 0;
        int end = nums.length - 1;
        // 因为每次拿到的都是最大值,所以只能从后往前赋值
        int index = nums.length - 1;

        while(start <= end){
            int s1 = nums[start] * nums[start];
            int s2 = nums[end] * nums[end];
            if(s1 > s2){
                nums[index--] = s1;
                start ++;
            }else{
                nums[index--] = s2;
                end --;
            }
        }
        return nums;
    }