题目练习：代码随想录解题思路分析

前言

其实博主从大二开始闲着没事陆续刷 leetcode 也刷了不少了，但是感觉都是没什么思想地刷，可能大多数题能记住解法，但是很多题再看到第一眼还是想不到什么双指针，滑窗之类的优解，没有这个意识，要扫一眼题解的方法才会恍然大悟“哦对哦可以这么做的”然后才能写出来。

所以这回（第 N 次为了面试做准备而重刷，从代码随想录开始，我还没试过这个）我决定重点在于“看到题目如何构思解法”的分析上。比如双指针一般应用于什么题型？为什么这道题看到后第一眼知道用双指针？

希望对你也有所帮助。

注：博主使用语言为 java。

数组

二分查找（Leetcode 704.）

时间复杂度是 log2(n)，空间复杂度 O(1)。

二分法使用的时候注意自己规定好左右边界，不要漏掉一些边界情况等。我的常用玩法是循环跳出条件为 left>right，每次校验完 mid 之后让 left=mid+1 或 right=mid-1。

class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length<=0)return -1;
        int left=0, right = nums.length-1;
        int mid=(left+right)/2;
        while(left<=right && nums[mid]!=target ){
            // nums[mid]>target?right=mid-1:left=mid+1;
            if(nums[mid]>target)right=mid-1;
            else left=mid+1;
            mid=(left+right)/2;
        }
        if(left>right)return -1;
        else return mid;
    }
}

移除数组指定值元素（Leetcode 27.）

如果没有原地的要求，我们新开辟一个数组空间，有选择性地把原数组值复制过去就行，记得记一下数看有多少个非 val 值。

GPT 总结双指针使用场景总览：

类型	描述	常见题型举例
1. 对撞指针	从两端向中间逼近	排序数组的和、回文串判断、三数之和等
2. 快慢指针	一快一慢遍历链表或数组	环形链表、删除重复元素、寻找中点等
3. 滑动窗口	左右指针控制一个动态区间	最小覆盖子串、最长无重复子串等
4. 区间遍历/合并区间	对多个数组或区间双向扫描	区间交集、归并两个有序数组等

class Solution {
    public int removeElement(int[] nums, int val) {
        int slowIndex = 0, fastIndex = 0;
        for (; fastIndex < nums.length; fastIndex++) {
            if(nums[fastIndex]!=val)nums[slowIndex++]=nums[fastIndex];
        }
        return slowIndex;
    }
}

有序数组的平方（Leetcode 977.）

这个题的关键点在于负数，也就是原数组按原顺序平方后得到的数组可能是先减后增的。

那么问题就变成怎么把负数那一部分按从小到大顺序插入到正数那一部分（我的理解），这和“合并两个数组”差不多。所以就是两个指针分别指向数组左右两端（负数绝对值的最大值和正数绝对值的最大值），每次拿出相对更大的一个放入到新数组中并移动该指针。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int leftIndex = 0, rightIndex = nums.length - 1;
        int resIndex = rightIndex;
        int[] resultNums = new int[nums.length];
        while (leftIndex <= rightIndex && resIndex >= 0) {
            int left = nums[leftIndex] * nums[leftIndex], right = nums[rightIndex] * nums[rightIndex];
            if (left > right) {
                resultNums[resIndex--] = left;
                leftIndex++;
            } else {
                resultNums[resIndex--] = right;
                rightIndex--;
            }
        }
        return resultNums;
    }
}

长度最小的子数组（Leetcode 209.）

从一个序列中找到符合标准的一个连续子序列，很明显的滑动窗口问题。

依然是双指针，确定左右边界。

每次循环先移动右指针，窗口 sum 值加上右指针指向的新值，如果超过 target 先试一试移动左指针后是否仍然满足（sum-当前左指针值，尽可能让满足条件的序列更短一些），如果不满足就不移动左指针了，然后比较记录当前子序列长度。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int left = 0, right = 0;
        int sum = 0;
        int minLength = nums.length + 1;
        for (; right < nums.length; right++) {
            sum += nums[right];
            if (sum >= target) {
                while (sum - nums[left] >= target) {
                    sum -= nums[left++];
                }
                if (right - left + 1 < minLength)
                    minLength = right - left + 1;
            }
        }
        if (minLength == nums.length + 1)
            return 0;
        return minLength;
    }
}

螺旋矩阵II（Leetcode 59.）

这个其实没啥难度，主要就是自己遍历的时候边界判定条件要统一，别自己写乱了。

做这种题我一般习惯于设置成下面这种 direction 矩阵，这样比较方便一些（学嵌入式时候的习惯）：

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] resMatrix = new int[n][n];
        int[] direction = { 0, 1, 1, 0, 0, -1, -1, 0 };
        int currentDirection = 0;
        int currentX = 0, currentY = 0;
        for (int i = 1; i <= n * n; i++) {
            resMatrix[currentX][currentY] = i;
            if (currentX + direction[currentDirection] < 0 ||
                    currentX + direction[currentDirection] >= n ||
                    currentY + direction[currentDirection + 1] < 0 ||
                    currentY + direction[currentDirection + 1] >=n ||
                    resMatrix[currentX + direction[currentDirection]][currentY
                            + direction[currentDirection + 1]] != 0) {
                currentDirection = (currentDirection + 2) % 8;
            }
            currentX = currentX + direction[currentDirection];
            currentY = currentY + direction[currentDirection + 1];
        }
        return resMatrix;
    }
}

区间和（代码随想录 58.）

主要练习一下 ACM 算法模式，整个程序都要自己写。

代码上，像这种需要区间求和的题目，如果每次都遍历求和就容易超时。取而代之的方法是搞一个 sum 数组，每个位置记录“从0位置到当前位置的所有元素和”（前缀和）。这个数组初始化的时候计算很方便，sum[i-1]+nums[i] 就可以了。求区间和的话就作差就行，sum[j]-sum[i-1]，注意 i=0 的时候单独处理。

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] vector = new int[n];
        for(int i=0;i<n;i++){
            vector[i]=sc.nextInt();
            if(i>0)vector[i]+=vector[i-1];
        }
        while(sc.hasNextInt()){
            int left=sc.nextInt();
            int right=sc.nextInt();
            if(left ==0)System.out.println(vector[right]);
            else System.out.println(vector[right]-vector[left-1]);
        }
        return ;
    }
}

开发商购买土地（代码随想录 44.)

这个是二维上的区间和，所以要点也是在于创造一个 sum 数组每个点存储当前位置的值+之前位置值之和（前缀和），通过 sum 数组值相减快速获取区间值，只不过变成两个维度了。

如果暴力求解的话，时间复杂度是 O(n^3)，每次选取一个维度进行遍历求该行或者列的求和值，再遍历组合所有分割可能的求和值的组合方式找到差值最小的情况。简化后变成 O(n^2).

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[][] matrix = new int[n][m];
        int[] row = new int[n];
        int[] column = new int[m];
        int minDiff = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
                row[i] += matrix[i][j];
                column[j] += matrix[i][j];
            }
        }
        for (int i = 1; i < n; i++) {
            row[i] += row[i - 1];
        }
        for (int i = 0; i < n; i++) {
            if (minDiff == -1 || minDiff > Math.abs(row[n - 1] - 2 * row[i]))
                minDiff = Math.abs(row[n - 1] - 2 * row[i]);
            if (minDiff == 0) break;
        }
        for (int i = 1; i < m; i++) {
            column[i] += column[i - 1];
        }
        for (int i = 0; i < m; i++) {
            if (minDiff == -1 || minDiff > Math.abs(column[m - 1] - 2 * column[i]))
                minDiff = Math.abs(column[m - 1] - 2 * column[i]);
            if (minDiff == 0) break;
        }
        System.out.println(minDiff);
        return;
    }
}

总结

数组可以说是必考的基础类型题目。主要考察算法就是二分法，双指针法，滑动窗口，前缀和。

数组在内存中是连续的存储空间，二维数组是多条连续的存储空间（两行之间地址不一定连续）。

Contact Me