理论
思维导图
子数组问题
- 刷题第一站
矩阵问题
- 刷题第一站
O(n)类型问题
- 刷题第一站
双指针
- 刷题第一站
分治
- 刷题第一站
  - 108. 将有序数组转换为二叉搜索树">108. 将有序数组转换为二叉搜索树
哈希法
- 刷题第一站 hasMap
  - LeetCcode 1 两数之和
  - LeetCode 454 四数相加 II
二分法
滑动窗口——初见
- 刷题第一站滑动窗口概念
  - LeetCode 209 长队最小的子数组
过程抽象
- 刷题第一站过程抽象
  - LeetCode
总结
- 经典题目

理论

数组是算法中最常用的一种数据结构，也是面试中最常考的考点。在LeetCode题库中，标记为数组类型的习题到目前为止，已累计到了202题。然而，这202道习题并不是每道题只标记为数组一个考点，大部分习题都有两到三个考点。比如，考查数组+哈希表、数组+动态规划+数学、数组+回溯等。
看到如此多考点标签，如果盲目地按照一个标签内部所有习题的顺序去刷题，会让人有点错乱感。对于时间比较紧凑的同学来说，题目的数量比较多，想在较短时间内刷完是一个很大的挑战。因此，本文针对时间较紧凑的同学精选一些数组类型的代表性题目，进行分类总结，希望能够起到一点帮助（PS：其实是作者希望借此进一步加深自己对考点的认知，建立一个有效的知识体系… …）。
标记为数组类型的题目有200多道题，本文的重点关注那些主要考察数组的题目。对于考察点主要放在其它考点（比如：二分查找、双指针、哈希表等）上的题目，作者计划把这些题目放在后序总结篇章中。按照作者刷题的情况，在属于数组考点系列的题目中，划分为四个常考问题：子数组问题、矩阵问题、O(n)类型问题和思维转换类型问题。

子数组问题：就是给定一个数组，围绕该数组的子数组列出诸多难题，等待我们来解答。
矩阵问题：给定一个矩阵（或者称为二维数组），围绕该矩阵列出不同方式遍历矩阵中元素等难题，等待我们来解答。
O(n)类型问题：O(n)是指时间复杂度为O(n)，给定的题目题意一般很容易理解，其一般解法（俗称暴力解法，时间复杂度一般为O(n^2)，甚至更高）也很简单，但是题目要求你的解法时间复杂度为O(n)。看到这些题目的某些解答后，会让我们忍不住夸赞：真乃神人、好厉害、奇异特解、巧妙、强、优雅。
思维转换类型问题：其解答不属于上述三种类型问题，但是解答方式有点巧妙，或者说该类型题目较为基础，很可能考察你的快速应用代码能力的题目。（PS: 其实是作者自己也不好划分，但是认为有点价值的题目… …）
思维导图

子数组问题

子数组问题：就是给定一个数组，围绕该数组的子数组列出诸多难题，等待我们来解答。

刷题第一站

53. 最大子序和

本体最为经典和广泛的解法是应用动态规划的思想来解答，其时间复杂度为O(N)。
从第一个元素开始遍历，用一个一位数组存储到当前元素的最大连续子数组的和。
dp[i]：表示以i元素结尾的子数组中最大子数组之和。
如果dp[i - 1] < 0，此时无益于nums[i]，则dp[i] = nums[i];否则dp[i] = dp[i - 1] + nums[i];
最后再遍历一遍求最大值，当然其实无需遍历的。

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int pre = nums[0]; // dp[i-1]
        int res = nums[0]; // 结果
        for (int i = 1; i < nums.length; i++) {
            int cur = pre < 0 ? nums[i] : pre + nums[i]; // dp[i]
            res = res > cur ? res : cur;
            pre = cur;
        }
        return res;
    }
}

152. 乘积最大子数组

这题其实是例1 最大子序和一个变例，由加法变换成了乘法操作（依旧是应用动态规划的思路）。此时需要做的改变是定义两个变量来存储当前子序列的乘积，一个是保存最大值，一个是保存最小值（包含负数的子序列）。

class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int preMax = nums[0];
        int preMin = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int cur = 1;
            if (nums[i] > 0) {
                cur = Math.max(nums[i], preMax * nums[i]);
                // 更新最大值和最小值
                preMax = cur;
                preMin = Math.min(nums[i] * preMin, nums[i]);
            } else {
                cur = Math.max(nums[i], preMin * nums[i]);
                // 更新最大值和最小值
                preMax = cur;
                preMin = Math.min(nums[i] * preMax, nums[i]);
            }
            res = Math.max(res, cur);
        }
        return res;
    }
}

但是我这个代码没有通过，真的难受，不清楚为什么。还是看官网代码吧！很简单，也很简洁。

class Solution {
    public int maxProduct(int[] nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; ++i) {
            int mx = maxF, mn = minF;
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            ans = Math.max(maxF, ans);
        }
        return ans;
    }
}

78. 子集

本题考查我们应用回溯来求解所有子集的问题
法一：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        subsetsHelpe(nums, 0, new ArrayList<Integer>(), res);
        return res;
    }
    // 站在这个节点处，该处理哪个数组下标了？现在形成的结果是什么？
    private void subsetsHelpe(int[] nums, int index, List<Integer> list, List<List<Integer>> res) {
        if (index == nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        list.add(nums[index]); // 选择一条路需要做的事情
        subsetsHelpe(nums, index + 1, list, res); // 选择一条路
        list.remove(list.size() - 1); // 回溯
        subsetsHelpe(nums, index + 1, list, res); // 选择另一条
    }
}

解法二：
数组 - 图2

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        subsetsHelpe(nums, new ArrayList<Integer>(), 0, res);
        return res;
    }
    // 站在这个节点处，该处理哪个数组下标了？现在形成的结果是什么？
    private void subsetsHelpe(int[] nums, List<Integer> list, int index, List<List<Integer>> res) {
        // if (index == nums.length) return;
        res.add(new ArrayList<>(list)); // 将每个节点都放入到集合中,即当前节点要做的事情
        for (int i = index; i <nums.length; i++) {
            list.add(nums[i]);
            subsetsHelpe(nums, list, i + 1, res);
            list.remove(list.size() - 1);
        }
    }
}

你有没有想过，我这里为什么把递归条件注释了？
1.如果不注释会发生什么情况？

2.注释后，还会结束吗？
会，自行判断。

90. 子集 II

这道题和上道题一样，只是需要在选择道路时剪枝罢了。
这里是用的上述题目的法二剪枝的，法一不好剪。以后有机会可以领悟一下法一的剪枝。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        subsetsHelpe(nums, new ArrayList<Integer>(), 0, res);
        return res;
    }

    // 站在这个节点处，该处理哪个数组下标了？现在形成的结果是什么？
    private void subsetsHelpe(int[] nums, List<Integer> list, int index, List<List<Integer>> res) {
        // if (index == nums.length) return;
        res.add(new ArrayList<>(list)); // 将每个节点都放入到集合中,即当前节点要做的事情
        for (int i = index; i <nums.length; i++) {
            if (i != index && nums[i] == nums[i - 1]) {
                continue;
            }
            list.add(nums[i]);
            subsetsHelpe(nums, list, i + 1, res);
            list.remove(list.size() - 1);
        }

    }
}

128. 最长连续序列

这道题不是动态规划。
采用哈希表存储数组中所有元素，然后应用哈希表查询当前元素的左右两边序列数字是否存在，查询操作的时间复杂度为O(1)。
思路及时间复杂度分析

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }

        int longestStreak = 0;

        for (int num : num_set) {
            if (!num_set.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

713. 乘积小于K的子数组

见岛这道题你是否想过是动态规划？？
但其实是双指针！！
本题考查应用双指针的思想，一前一后同时往后遍历。
但但其实是窗口。但好像又不是窗口。又好像是，我也无法区分，太菜了。
啊啊啊啊啊

这道题不会，后面再想下。

560. 和为K的子数组

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, 1); // 这个一定要写，否则过不了的
        int count = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 对于每个数，看前面含有多少数 = k - nums[i]
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            // 将当前数前面的和放入map
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

974. 和可被 K 整除的子数组

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        Map<Integer, Integer> record = new HashMap<>();
        record.put(0, 1);
        int sum = 0, ans = 0;
        for (int elem : A) {
            sum += elem;
            // 注意 Java 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
            int modulus = (sum % K + K) % K;
            int same = record.getOrDefault(modulus, 0);
            ans += same;
            record.put(modulus, same + 1);
        }
        return ans;
    }
}

689. 三个无重叠子数组的最大和

动态规划，不会做，这个。

718. 最长重复子数组

解法一：动态规划

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2.length == 0 || nums2.length == 0) return -1;
        int[][] dp = new int[nums1.length][nums2.length];
        int res = 0;
        for (int i = 0; i < nums2.length; i++) {
            dp[0][i] = nums1[0] == nums2[i] ? 1 : 0;
            res = Math.max(res, dp[0][i]);
        }
        for (int i = 0; i < nums1.length; i++) {
            dp[i][0] = nums1[i] == nums2[0] ? 1 : 0;
            res = Math.max(res, dp[i][0]);
        }
        for (int i = 1; i < nums1.length; i++) {
            for (int j = 1; j < nums2.length; j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 0;
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }
}

官网的另外两种解法没有看懂！

792. 匹配子序列的单词数

官网解析
话不多说，看官网解析吧！自己现在还写不出来优化的。

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int ans = 0;
        // 建桶，共26个桶，每个桶放的都是字符串(可能是多个)，以字符串的待判断字符确定放在哪个桶
        ArrayList<Node>[] buckets = new ArrayList[26];
        // 初始化桶，即每个里面放置一个空的List
        /*for (ArrayList<Node> bucket : buckets) { // 这种只可遍历，不可赋值
            bucket = new ArrayList<Node>();
        }*/
        for (int i = 0; i < 26; i++) {
            buckets[i] = new ArrayList<Node>();
        }

        // 再次初始化，准确地说，是将words放入桶中(根据待判断位置)
        for (String word : words) {
            buckets[word.charAt(0) - 'a'].add(new Node(word, 0));
        }

        // 遍历字符串s，开始判断
        for (char c : s.toCharArray()) {
            // 对于当前字符，去取出桶中数据(当然里面可能没有数据)
            ArrayList<Node> datas = buckets[c - 'a']; // 引用出来的这个桶中的数据里面可能没有
            // 此时该数组位置里面的数据应该清空，即重新生成一个链表，为什么不用原来的呢？即原有的clear.因为后面我们要放数据(用空间)且要用原有数据
            buckets[c - 'a'] = new ArrayList<Node>();

            // 遍历得到的数据：如果index已经来到末尾，则ans++，否则将其重新换桶
            for (Node data : datas) {
                data.index++;
                if (data.index == data.word.length()) {
                    ans++;
                } else {
                    buckets[data.word.charAt(data.index) - 'a'].add(data);
                }
            }
        }
        return ans;
    }
}

class Node {
    String word;
    int index; // 待判断位置
    public Node(String word, int index) {
        this.word = word;
        this.index = index;
    }
}

795. 区间子数组个数

我裂开了，这题解，我的天啊！！
本题官网题解
最大元素满足大于等于L小于等于R的子数组个数 = 最大元素小于等于R的子数组个数 - 最大元素小于L的子数组个数。
几道前缀和题目，暂时没时间做链接

class Solution {
    public int numSubarrayBoundedMax(int[] A, int L, int R) {
        return count(A, R) - count(A, L - 1);
    }
    private int count(int[] A, int bound) {
        int ans = 0; // 整个数组中<=bound子数组个数
        int cur = 0; // 以当前index结尾的子数组中<=bound的子数组个数
        for (int num : A) {
            cur = num <= bound ? cur + 1 : 0;
            ans += cur;
        }
        return ans;
    }
}

907. 子数组的最小值之和

单调栈
这道题做出来了，但是在LeetCode没有通过，应该是我取模哟问题吧！暂时不知怎么解决。
下面再来几道单调栈题目！题解
 链接一
 链接二

class Solution {
    // 用单调栈寻找每个元素左右两侧最近的≤num的数的下标
    public int sumSubarrayMins(int[] arr) {
        int MOD = 1_000_000_007;
        int ans = 0;
        Stack<Integer> stack = new Stack<Integer>();

        for (int  i = 0; i < arr.length; i++) { // 处理每一个元素
            // 待压入元素≥栈顶元素，就结算栈顶元素
            while (!stack.isEmpty() && arr[i] <= arr[stack.peek()]) { // 出现这种情况就结算
                int index = stack.pop(); // 结算是以该元素为中心
                int right = i; // 右边界
                int n = right - index - 1;
                int left = stack.isEmpty() ? -1 : stack.peek(); // 左边界
                int m = index - left - 1;
                ans += (m + 1 + n + m * n) * arr[index] % MOD;
                ans %= MOD;
            }
            stack.push(i); // 这个是无论栈为空，还是栈顶元素≥当前元素，还是栈顶元素<当前元素，都将当前元素压入
        }

        // 结算栈中剩余元素
        while (!stack.isEmpty()) {
            int index = stack.pop(); // 结算是以该元素为中心
            int right = arr.length; // 右边界
            int n = right - index - 1;
            int left = stack.isEmpty() ? -1 : stack.peek(); // 左边界
            int m = index - left - 1;
            ans += (m + 1 + n + m * n) * arr[index] % MOD;
            ans %= MOD;
        }
        return ans % MOD;
    }
}

891. 子序列宽度之和

这道题暂时不写了，推导好复杂！！
推导

918. 环形子数组的最大和

数组 - 图6
其实Kadane就是最大连续子数组和问题，就是动态规划。
因为题目要求有环形，所以需要定义两个变量。一个变量存储当前无环形是的连续最大子数组和，一个存储无环形连续最小子数组和。最后采用数组的总和减去最小和，和已经保存的最大和进行比较。另外，需要注意一点如果数组全部为负数时，此时直接返回子数组的最大值（因为此时，最小子数组和就是数组的和）。

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        if (A == null || A.length == 0) return -1;
        if (A.length == 1) return A[0];
        int[] minDP = new int[A.length];
        minDP[0] = A[0];
        int[] maxDP = new int[A.length];
        maxDP[0] = A[0];
        int min = A[0];
        int max = A[0];
        int sum = A[0];
        for (int i = 1; i < A.length; i++) {
            sum += A[i];
            minDP[i] = Math.min(A[i], A[i] + minDP[i - 1]);
            min = Math.min(min, minDP[i]);
            maxDP[i] = Math.max(A[i], A[i] + maxDP[i - 1]);
            max = Math.max(max, maxDP[i]);
        }

        // 如果sum==min时，要返回max，比如[-3,-2,-1]，否则会报错
        return  sum == min ? max : Math.max(max, sum - min);
    }
}

978. 最长湍流子数组

解法一：滑动窗口

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int ans = 1;
        int left = 0, right = 0;
        while (right < n - 1) {
            if (left == right) {
                if (arr[left] == arr[left + 1]) {
                    left++;
                }
                right++;
            } else {
                if (arr[right - 1] < arr[right] && arr[right] > arr[right + 1]) {
                    right++;
                } else if (arr[right - 1] > arr[right] && arr[right] < arr[right + 1]) {
                    right++;
                } else {
                    left = right;
                }
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

解法二：动态规划

class Solution {
    public int maxTurbulenceSize(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][2];
        dp[0][0] = dp[0][1] = 1;
        int ans = 1;
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i][1] = 1;
            if (arr[i] > arr[i - 1]) {
                dp[i][1] = dp[i - 1][0] + 1;
            } else if (arr[i] < arr[i - 1]) {
                dp[i][0] = dp[i - 1][1] + 1;
            }
            ans = Math.max(ans, Math.max(dp[i][0], dp[i][1]));
        }

        return ans;
    }
}

1031. 两个非重叠子数组的最大和

这道题不会做

1157. 子数组中占绝大多数的元素

这道题的建档方法很好写，比如借助hashMap，但是复杂的不懂。

矩阵问题

子数组问题：就是给定一个数组，围绕该数组的子数组列出诸多难题，等待我们来解答。
矩阵问题：给定一个矩阵（或者称为二维数组），围绕该矩阵列出不同方式遍历矩阵中元素等难题，等待我们来解答。
O(n)类型问题：O(n)是指时间复杂度为O(n)，给定的题目题意一般很容易理解，其一般解法（俗称暴力解法，时间复杂度一般为O(n^2)，甚至更高）也很简单，但是题目要求你的解法时间复杂度为O(n)。看到这些题目的某些解答后，会让我们忍不住夸赞：真乃神人、好厉害、奇异特解、巧妙、强、优雅。
思维转换类型问题：其解答不属于上述三种类型问题，但是解答方式有点巧妙，或者说该类型题目较为基础，很可能考察你的快速应用代码能力的题目。（PS: 其实是作者自己也不好划分，但是认为有点价值的题目… …）

矩阵也可以称为二维数组。在LeetCode相关习题中，作者总结的考点有：矩阵元素的遍历、矩阵位置的旋转、矩阵行或列次序的交换、空间复杂度为O(1)等。本期共12道题，2道简单题，8道中等题，2道困难题。

例1是杨辉三角的一个延申题，是一道非常经典的矩阵习题，本题理想解法是动态规划，但是也可以采用递归来求解。
例2是一道顺时针访问矩阵元素的习题，在不少面试题中有见到。
例3、例4和例5则强调如何利用矩阵本身的空间，来变换矩阵中的元素，即空间复杂度为O(1)。用到了元素间交换和位运算策略，其中相关解法很巧妙。
例6是一道如何移动矩阵的问题。
例7和例8则是考察我们快速理解题意，并在较短时间内完成较高质量代码的能力。即编写的代码争取一次性通过。
例9考察我们如何把二分查找的应用场景由一维数组转换到二维数组。
例10是一道动态规划结合矩阵的经典习题，并且还可以延申出求最短路径的问题。
例11则很有意思，该题是 和为k的子数组 的一个升级版，把一维数组的场景变换成了二维的场景，并结合了动态思想，因此题目难度由中等变成了困难。

例12是一道困难级别的习题，该题主要考察我们的数学分析能力，如何灵活变换矩阵的行和列，以及细节的处理能力。

刷题第一站

118. 杨辉三角

数组 - 图7

class Solution {
  public List<List<Integer>> generate(int numRows) {
      List<List<Integer>> ret = new ArrayList<List<Integer>>();
      for (int i = 0; i < numRows; i++) {
          List<Integer> row = new ArrayList<Integer>();
          for (int j = 0; j <= i; j++) {
              if (j == 0 || j == i) {
                  row.add(1);
              } else {
                  row.add(ret.get(i - 1).get(j) + ret.get(i - 1).get(j - 1));
              }
          }
          ret.add(row);
      }
      return ret;
  }
}

119. 杨辉三角 II

依据杨辉三角的规律，当前行的数据和上一行的数据有着递推关系：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。依据该递推公式可以写一个较为清晰的动态规划解法，其空间复杂度为O(k)。但是，也可以采用递归的思想来解决。此处提供一个应用递归思想来解决该问题的代码。
优化前

class Solution {
  public List<Integer> getRow(int rowIndex) {
      List<List<Integer>> C = new ArrayList<List<Integer>>();
      for (int i = 0; i <= rowIndex; ++i) {
          List<Integer> row = new ArrayList<Integer>();
          for (int j = 0; j <= i; ++j) {
              if (j == 0 || j == i) {
                  row.add(1);
              } else {
                  row.add(C.get(i - 1).get(j - 1) + C.get(i - 1).get(j));
              }
          }
          C.add(row);
      }
      return C.get(rowIndex);
  }
}

滚动数组优化
注意到对第i+1行的计算仅用到了第ii行的数据，因此可以使用滚动数组的思想优化空间复杂度。

class Solution {
  public List<Integer> getRow(int rowIndex) {
      List<Integer> pre = new ArrayList<Integer>();
      for (int i = 0; i <= rowIndex; i++) {
          List<Integer> cur = new ArrayList<Integer>();
          for (int j = 0; j <= i; ++j) {
              if (j == 0 || j == i) {
                  cur.add(1);
              } else {
                  cur.add(pre.get(j) + pre.get(j - 1));
              }
          }
          pre = cur;
      }
      return pre;
  }
}

54. 螺旋矩阵
该题已完成！

48. 旋转图像

class Solution {
  public void rotate(int[][] matrix) {
      int tR = 0;
      int tC = 0;
      int dR = matrix.length - 1;
      int dC = matrix[0].length - 1;
      while (tR < dR) { // tR == dR这个不用旋转了
          helper(matrix, tR++, tC++, dR--, dC--);
      }
  }
  private void helper(int[][] matrix, int tR, int tC, int dR, int dC) {
      for (int i = 0; i < dC - tC; i++) {
          int temp = matrix[dR - i][tC];
          matrix[dR - i][tC] = matrix[dR][dC - i];
          matrix[dR][dC - i] = matrix[tR + i][dC];
          matrix[tR + i][dC] = matrix[tR][tC + i];
          matrix[tR][tC + i] = temp;
      }
  }
}

73. 矩阵置零

实话说，都是鬼才。
方法一：当然LeetCode不让使用这种方法。
数组 - 图8
先说一下空间复杂度为O(m+n)的思路（PS：该思路不符合题意的原地算法要求）。申请两个一维数组，一个表示矩阵行，一个表示矩阵列。然后，遍历矩阵中所有元素，一旦出现零，把该零对应行和对应列的一维数组的值标记为常数1。最后，分别按行和按列给原始矩阵赋值零。

class Solution {
  public void setZeroes(int[][] matrix) {
      int m = matrix.length;
      int n = matrix[0].length;
      boolean[] row = new boolean[m];
      boolean[] col = new boolean[n];

      for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
              if (matrix[i][j] == 0) {
                  row[i] = true;
                  col[j] = true;
              }
          }
      }

      for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
              if (row[i] || col[j]) {
                  matrix[i][j] = 0;
              }
          }
      }      
  }
}

现在参考LeetCode上一个评论的思路，空间复杂度为O(2)。申请两个布尔变量cow和col，分别记录原矩阵第0行和第0列中是否存在零，如果存在标记为True，否则标记为False。然后，接下来的思路就是上面O(m+n)的解决思路，唯一不同的是此时的空间是采用原始矩阵的空间。

class Solution {
  public void setZeroes(int[][] matrix) {
      boolean colFlag = false;
      boolean rowFlag = false;
      int m = matrix.length, n = matrix[0].length;
      for (int i = 0; i < m; i++) {
          if (matrix[i][0] == 0) {
              colFlag = true;
          }
      }
      for (int i = 0; i < n; i++) {
          if (matrix[0][i] == 0) {
              rowFlag = true;
          }
      }

      for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++) {
              if (matrix[i][j] == 0) {
                  matrix[i][0] = 0;
                  matrix[0][j] = 0;
              }
          }
      }
      for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++) {
              if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                  matrix[i][j] = 0;
              }
          }
      }
      if (colFlag) {
          for (int i = 0; i < m; i++) {
              matrix[i][0] = 0;
          }
      }

      if (rowFlag) {
          for (int i = 0; i < n; i++) {
              matrix[0][i] = 0;
          }
      }
  }
}

289. 生命游戏

这个问题看起来很简单，但有一个陷阱，如果你直接根据规则更新原始数组，那么就做不到题目中说的同步更新。假设你直接将更新后的细胞状态填入原始数组，那么当前轮次其他细胞状态的更新就会引用到当前轮已更新细胞的状态，但实际上每一轮更新需要依赖上一轮细胞的状态，是不能用这一轮的细胞状态来更新的。
已更新细胞的状态会影响到周围其他还未更新细胞状态的计算。一个最简单的解决方法就是复制一份原始数组，复制的那一份永远不修改，只作为更新规则的引用。这样原始数组的细胞值就不会被污染了。
但这种解法不是题目想要的。
因此我们要想办法记录原有的数据状态和现在新的数据状态。
数组 - 图9
数组 - 图10
这个代码是我抄袭的，要多学学人家的代码！！

class Solution {
  public void gameOfLife(int[][] board) {
      int[] neighbors = {-1, 0, 1};

      int rows = board.length;
      int cols = board[0].length;

      // 遍历面板每一个格子里的细胞
      for (int row = 0; row < rows; row++) {
          for (int col = 0; col < cols; col++) {
              // 对于每一个细胞同级其八个相邻位置里的活细胞数量
              int liveNeighbors = 0;
              for (int i = 0; i < 3; i++) {
                  for (int j = 0; j < 3; j++) {
                      if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                          // 相邻位置的坐标
                          int r = row + neighbors[i];
                          int c = col + neighbors[j];

                          // 查看相邻的细胞是否是活细胞
                          if ((r < rows && r >= 0) && (c < cols && c >= 0) && (Math.abs(board[r][c]) == 1)) {
                              liveNeighbors++;
                          }
                      }
                  }
              }

              // 规则 1 或规则 3
              if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
                  // -1 代表这个细胞过去是活的现在死了
                  board[row][col] = -1;
              }
              // 规则 4
              if (board[row][col] == 0 && liveNeighbors == 3) {
                  // 2 代表这个细胞过去是死的现在活了
                  board[row][col] = 2;
              }
          }
      }
      // 遍历 board 得到一次更新后的状态
      for (int row = 0; row < rows; row++) {
          for (int col = 0; col < cols; col++) {
              if (board[row][col] > 0) {
                  board[row][col] = 1;
              } else {
                  board[row][col] = 0;
              }
          }
      }
  }
}

835. 图像重叠

先不做了！

999. 可以被一步捕获的棋子数

数组 - 图11
本题较为简单，直接遍历矩阵找到车的位置，然后在车能行走的四个方向依次遍历即可。（放入此题的意图，题目比较长，读懂题意需要耗费一些时间，另外编写代码需要注意边界问题）

class Solution {
  public int numRookCaptures(char[][] board) {
      int cnt = 0, st = 0, ed = 0;
      int[] dx = {0, 1, 0, -1};
      int[] dy = {1, 0, -1, 0};
      for (int i = 0; i < 8; i++) {
          for (int j = 0; j < 8; j++) {
              if (board[i][j] == 'R') {
                  st = i;
                  ed = j;
                  break;
              }
          }
      }

      for (int i = 0; i < 4; i++) {
          for (int step = 0;; step++) {
              int tx = st + step * dx[i];
              int ty = ed + step * dy[i];
              if (tx < 0 || tx >= 8 || ty < 0 || ty >=8 || board[tx][ty] == 'B') {
                  break;
              }
              if (board[tx][ty] == 'p') {
                  cnt++;
                  break;
              }
          }
      }
      return cnt;
  }
}

1222. 可以攻击国王的皇后

此题是例7的一个小小的升级版，重点还是处理边界问题，以及快速编写代码和一次通过的能力。
这道题和上一道的解法一模一样，只是这里用的方向数组有所变化。当然其实本质是一样的。
这种题的整个思路是，1.列举每个方向，2.在这个方向延伸步子；3.判断或break中止延伸。

class Solution {
  public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
      List<List<Integer>> ans = new ArrayList<List<Integer>>();
      int st = king[0], ed = king[1];
      int[] neighbors = {-1,0,1};
      for (int i = 0; i < 3; i++) {
          for (int j = 0; j < 3; j++) {
              if (!(neighbors[i] == 0 && neighbors[j] == 0)) { // 说明就是九个方向中国的一个
                  // 列举向这个方向行进的步数
                  for (int step = 0;; step++) {
                      int tx = st + step * neighbors[i];
                      int ty = ed + step * neighbors[j];
                      if (tx < 0 || tx >= 8 || ty < 0 || ty >= 8) {
                          break;
                      }
                      if (isQueens(queens, tx, ty)) {
                          List<Integer> point = new ArrayList<Integer>();
                          point.add(tx);
                          point.add(ty);
                          ans.add(point);
                          break; // 找到一个后，下面的就不用管了
                      }
                  }
              }
          }
      }
      return ans;
  }
  private boolean isQueens(int[][] queens, int tx, int ty) {
      for (int i = 0; i < queens.length; i++) {
          if (queens[i][0] == tx && queens[i][1] == ty) {
              return true;
          }
      }
      return false;
  }
}

74. 搜索二维矩阵
这道题已经做过了，这里再做一遍。

class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
      int rows = matrix.length, cols = matrix[0].length;
      int left = 0, right = rows * cols - 1;
      while (left + 1 < right) {
          int mid = left + ((right - left) >> 1);
          int row = mid / cols;
          int col = mid % cols;
          if (matrix[row][col] == target) {
              return true;
          } else if (matrix[row][col] < target) {
              left = mid;
          } else {
              right = mid;
          }
      }
      if (matrix[left / cols][left % cols] == target) {
          return true;
      }
      if (matrix[right / cols][right % cols] == target) {
          return true;
      }
      return false;
  }
}

64. 最小路径和
这道题也做过了！
动态规划，没什么说的！

class Solution {
  public int minPathSum(int[][] grid) {
      int[][] dp = new int[grid.length][grid[0].length];
      for (int i = 0; i < grid.length; i++) {
          if (i == 0) {
              dp[i][0] = grid[i][0];
          } else {
              dp[i][0] = dp[i - 1][0] + grid[i][0];
          }
      }
      for (int i = 0; i < grid[0].length; i++) {
          if (i == 0) {
              dp[0][i] = grid[0][i];
          } else {
              dp[0][i] = dp[0][i - 1] + grid[0][i];
          }
      }
      for (int i = 1; i < grid.length; i++) {
          for (int j = 1; j < grid[0].length; j++) {
              dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
          }
      }
      return dp[grid.length - 1][grid[0].length - 1];
  }
}

1074. 元素和为目标值的子矩阵数量

这道题这个基本的前缀和+暴力解法是很好做的。但是不知道好不好。

class Solution {
  public int numSubmatrixSumTarget(int[][] matrix, int target) {
      int rows = matrix.length;
      int cols = matrix[0].length;
      int[][] dp = new int[rows][cols];
      for (int i = 0; i < cols; i++) {
          if (i == 0) {
              dp[0][i] = matrix[0][i];
          } else {
              dp[0][i] = dp[0][i - 1] + matrix[0][i];
          }
      }
      for (int i = 1; i < rows; i++) {
          int sum = 0;
          for (int j = 0; j < cols; j++) {
              sum += matrix[i][j];
              dp[i][j] = dp[i - 1][j] + sum;
          }
      }
  }
}

782. 变为棋盘

先不做了！

O(n)类型问题

刷题第一站

本期讲O(n)类型问题，共14题。3道简单题，9道中等题，2道困难题。数组篇共归纳总结了50题，本篇是数组篇的最后一篇。
本系列50道题是作者在LeetCode题库数组标签中包含的202道题中，按照解答考点分类归纳总结的题型。解法仅供参考，主要在于题目和考点的分类。希望对准备刷LeetCode，而感觉题目繁多、标签太多、时间较少，不知道从何开始刷题的同学一点小小的帮助^~^。
数组 - 图12

双指针

双指针可以将原本复杂度是O(N2)的问题，即两次遍历问题，转化成一次遍历。

刷题第一站

LeetCode 27 移除元素

解法一——当被删除元素较少时
保留两个指针 i 和 j，其中 i 是慢指针，j是快指针。这里是for循环。
对于j是for循环遍历每一个待处理的元素；对于i则是指向当前有效元素的下标，当然，初始化是0。
对于待处理元素，如果等于被删除元素，则直接跳过；否则，将其移动到i下标位置，i++

public int removeElement(int[] nums, int val) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

时间复杂度O(N)
假设数组总共有 n个元素，i和 j至少遍历 2n 步。
空间复杂度O(1)
解法二——当被删除元素较多时
上面的策略是针对不被删除的元素移位，因此当被删除元素较少时更合适。如果删除元素较多时，则可以采用另一种策略，当然还是双指针。
此时还是有一个遍历数组指针，另一个指针则是指向有效元素的末尾。
对于遍历的元素，如果遇到需要被删除的，将末尾元素copy过来即可，细节见代码。

class Solution {
    /**
    * 思路：
    * 遍历每个元素，如果遇到需要被原地删除的，则将最后一个元素移至这里
    */
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int end = nums.length - 1; // 0~end都是有效元素
        int index = 0;
        while (index <= end) { // 这里为什么不用for循环，因为for是每个元素遍历一遍，而这里可能要某个下标元素遍历两次
            if (nums[index] == val) {
                nums[index] = nums[end--];
            } else {
                index++;
            }
        }
        return end + 1;
    }
}

时间复杂度：O(n)，i 和 n 最多遍历 n 步。在这个方法中，赋值操作的次数等于要删除的元素的数量。因此，如果要移除的元素很少，效率会更高。

空间复杂度：O(1)。

LeetCode 26 删除有序数组中的重复项

解法一——保留重复元素中最后一个
这道题和上面题目解法一非常相像，因此放在一起。
解法：还是快慢指针
慢指针i开始指向0位置
快指针j遍历数组，对于每个待处理元素要做如下判断：
1.如果这个元素和后面元素不重复，则copy到慢指针处；
2.如果这个元素和后面元素重复，则快指针定位到最后一个元素处，再copy到慢指针处。
即对于当前元素，如果没有下一个，或者有下一个且和下一个不同，直接copy；如果有下一个且和下一个相同，则不处理该元素，因为这个元素无用

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (j == nums.length - 1 || nums[j] != nums[j + 1]) {
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}

解法二——保留重复元素中第一个
这个解法和上面是一样的，只是是LeetCode的代码，我写在下面。
数组完成排序后，我们可以放置两个指针 i 和 j，其中i 是慢指针，而 j 是快指针。只要 nums[i] = nums[j]，我们就增加 j以跳过重复项。
当遇到nums[i] != nums[j]跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i + 1]。然后递增 i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止。

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                nums[++i] = nums[j];
            }
        }
        return i + 1;
    }
}

复杂度分析

时间复杂度：O(n)，假设数组的长度是 n，那么 i 和 j 分别最多遍历 n 步。
空间复杂度：O(1)。
LeetCode 15 三数之和
这道题和LeetCode 1 两数之和非常相似，都是经典面试题，但解法却不相同。
解法一：
这段导体的暴力解法是O(N3)的，也就是三层循环遍历一下，但是呢？你要考虑去重问题，因为最终结果中不能有重复数据。
这里重复问题的解决比较棘手。
解法二：
将所有数都添加在HashMap中，然后用两层循环遍历，这样可以在O(1)的时间内看第三个数target-sumTwo是否存在map中。但是这种解法同样会面对重复问题。
因此这道题不适合用哈希法。
解法三：排序+双指针
这里排序是为了解决重复问题，同时解决双指针移动问题。

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下表0的地方开始，同时定一个下表left 定义在i+1的位置上，定义下表right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i] b = nums[left] c = nums[right]。

接下来如何移动left 和right呢，如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下表就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

时间复杂度：O(n^2)。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // 需要和上一个枚举的数不相同
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1; // 左指针
            int right = nums.length - 1; // 右指针
            while (left < right) {
                // 左指针枚举的数和上一次不能相同
                while (left > i + 1  && left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                // 右指针亦如此
                while (right != nums.length - 1  && right > left && nums[right] == nums[right + 1]) {
                    right--;
                }
                // 由于双指针移动了，因此还要判断双指针是否失效
                if (left < right) {
                    // 此时双指针有效，三数之和有三种情况
                    if (nums[i] + nums[left] + nums[right] > 0) {
                        right--;
                    } else if (nums[i] + nums[left] + nums[right] < 0) {
                        left++;
                    } else {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(nums[i]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        res.add(list);
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

这里贴另外一个景点代码共参考：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            // 错误去重方法，将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            // 正确去重方法
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                } else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};

LeetCode 18 四数之和

四数之和，和三数之和是一个思路，都是使用双指针法, 基本解法就是在三数之和的基础上再套一层for循环。
但是有一些细节需要注意，例如：不要判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。（大家亲自写代码就能感受出来）
三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下表作为双指针，找到nums[i] + nums[left] + nums[right] == 0。
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下表作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n2)，四数之和的时间复杂度是O(n3) 。
那么一样的道理，五数之和、六数之和等等都采用这种解法。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // 保证这次选择数据和上一次不重复
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                // 保证这次选择数据和上一次不重复
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                // 双指针
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    // 保证左指针和上次选择的不一样
                    while (left != j + 1 && left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    // 右侧亦如此
                    while (right != nums.length - 1 && left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                    if (left < right) {
                        if (nums[i] + nums[j] + nums[left] + nums[right] < target) {
                            left++;
                        } else if (nums[i] + nums[j] + nums[left] + nums[right] > target) {
                            right--;
                        } else {
                            List<Integer> list = new ArrayList<>();
                            list.add(nums[i]);
                            list.add(nums[j]);
                            list.add(nums[left++]);
                            list.add(nums[right--]);
                            res.add(list);
                        }
                    }
                }

            }
        }
        return res;
    }
}

这里再贴一个别人博客的解法，和三数之和代码来源对应。
代码随想录

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 这种剪枝是错误的，这道题目target 是任意值 
            // if (nums[k] > target) {
            //     return result;
            // }
            // 去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 正确去重方法
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    if (nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    } else if (nums[k] + nums[i] + nums[left] + nums[right] < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 去重逻辑应该放在找到一个四元组之后
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }

};

链表

双指针在链表中应用，会在链表部分展示：
如：

分治

刷题第一站

108. 将有序数组转换为二叉搜索树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null) return null;
        return helper(nums, 0, nums.length - 1);
    }
    private TreeNode helper(int[] nums, int left, int right) {
        if (left == right) return new TreeNode(nums[left]);
        if (right < left) return null;
        int mid = left + ((right - left) >> 1);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }
}

哈希法

这里依然是数组的题目，只是有一些题目是借助hashMap、hashSet或者是借助数组充当hash来解决。

刷题第一站 hasMap

LeetCcode 1 两数之和

这道题的暴力解法显然是O(n2)的，这显然不是你我想要的。
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

很显然这里使用哈希法最为合适，之前已经介绍过，数组和set在哈希法中的应用，那么来看一下使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下表位置，因为要返回x 和 y的下表。所以set 也不能用。

此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下表。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[] {i, map.get(target - nums[i])};
            } else {
                map.put(nums[i], i);
            }
        }
        return new int[0];
    }
}

思考：
结合LeetCode 15 三数之和，思考这道题是否可以用二分法
答案：不可以。如果这个数组排序则可以。

LeetCode 454 四数相加 II

本题咋眼一看好像和第18题. 四数之和，第15题.三数之和差不多，其实差很多。
「本题是使用哈希法的经典题目，而第18题. 四数之和，第15题.三数之和并不合适使用哈希法」，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。
「而这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！」
如果本题想难度升级：就是给出一个数组（而不是四个数组），在这里找出四个元素相加等于0，答案中不可以包含重复的四元组，大家可以思考一下，后续的文章我也会讲到的。
本题解题步骤：

首先定义一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
定义int变量count，用来统计a+b+c+d = 0 出现的次数。
在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。

最后返回统计值 count 就可以了

class Solution {
 public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
     Map<Integer, Integer> map = new HashMap<>();
     int count = 0;
     for (int i = 0; i < A.length; i++) {
         for (int j = 0; j < B.length; j++) {
             if (map.containsKey(A[i] + B[j])) {
                 map.put(A[i] + B[j],map.get(A[i] + B[j]) + 1);
             } else {
                 map.put(A[i] + B[j], 1);
             }
         }
     }
     for (int i = 0; i < C.length; i++) {
         for (int j = 0; j < D.length; j++) {
             if (map.containsKey(0 - C[i] - D[j])) {
                 count += map.get(0 - C[i] - D[j]);
             }
         }
     }
     return count;
 }
}

二分法

二分法：
1.Recursion or While-Loop？尽量不递归，耗费栈空间。面试时如果递归简单，当然优先递归。

寻找target无非就两类，一类是first target；一类是last target。见到一道题，我们首先要确认是寻找sirst position还是last position。
二分法就是找临界点：第一个或最后一个
start 和 end在开始就保证答案就在里面(当然，前提得有答案，然后不断缩小空间，最后在剩余空间中判断)
logN的辅助度，80%都是二分法
做题先画图

所有题都转换为：寻找first position或last position
二分搜索模板
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.
If the target number does not exist in the array, return -1.
Example If the array is 1, 2, 3, 3, 4, 5, 10, for given target 3, return 2.

class Solution {
    public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                end = mid;
            } else if (nums[mid] < target) {
                start = mid;
                // or start = mid + 1
            } else {
                end = mid;
                // or end = mid - 1
            }
        }
        // 此时范围已缩小到两个元素
        // 这最后是剩下两个元素后，再与target比较
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

四点要素：

start + 1 < end
start + (end - start) / 2
A[mid] ==, <, >

A[start] A[end] ? target 这个根据是first position还是last position设置放置顺序。

刷题第一站 first or last

该站题目都是升序数组，是最常见，最普通的二分搜索。
这一站的题目非常简单，只需要判别出示寻找first position，还是last position。然后套用模板即可。
因此我们要将题目化为first position，还是last position。

LeetCode 704 二分查找

该题无所谓first position还是last position，有就返回角标，没有就返回-1.

class Solution {
 public int search(int[] nums, int target) {
     if (nums == null || nums.length == 0) {
         return -1;
     }
     int start = 0, end = nums.length - 1;
     while (start + 1 < end) {
         int mid = start + (end - start) / 2;
         if (nums[mid] == target) {
             return mid;
         } else if (nums[mid] < target) {
             start = mid;
         } else {
             end = mid;
         }
     }
     // 此时范围已缩小到两个元素
     // 由于无所依首还是未，因此无顺序。
     if (nums[start] == target) {
         return start;
     }
     if (nums[end] == target) {
         return end;
     }
     return -1;
 }
}

LeetCode 35 搜索插入位置

class Solution {
 // 寻找第一个>= target的位置
 public int searchInsert(int[] nums, int target) {
     if (nums == null) {
         return -1;
     }
     if (nums.length == 0) {
         return 0;
     }
     int start = 0, end = nums.length - 1;
     while (start + 1 < end) {
         int mid = start + (end - start) / 2;
         if (nums[mid] >= target) {
             end = mid;
         }else {
             start = mid;
         }
     }
     // 此时就是剩下两个元素了(范围缩小到此了)，然后你思考target该插入到哪里
     if (nums[start] >= target) {
         return start;
     }
     if (nums[end] < target) {
         return end + 1;
     }
     return end;
 }
}

LeetCode 74 搜索二维矩阵

这道题读完就知道，其实就是一个升序序列。只是以前这个生序序列在一维数组中，此时换成了二维数组。
如果你第一次见到这道题目，可能会有些陌生，不知道如何将这个二维数组视为一维数组看待。

class Solution {
 // 无所谓首尾，找到即可
 public boolean searchMatrix(int[][] matrix, int target) {
     if (matrix == null || matrix[0] == null || matrix.length == 0 || matrix[0].length == 0) {
         return false;
     }
     // 备用数据，方便计算当前mid点在几行，几列
     int rows = matrix.length, cols = matrix[0].length;
     int start = 0, end = rows * cols - 1;
     while (start + 1 < end) {
         int mid = start + (end - start) / 2;
         if (matrix[mid / cols][mid % cols] == target) {
             return true;
         } else if (matrix[mid / cols][mid % cols] > target) {
             end = mid;
         } else {
             start = mid;
         }
     }
     // 最后剩下两个
     // 无所谓首位，找到即可
     if (matrix[start / cols][start % cols] == target || matrix[end / cols][end % cols] == target) {
         return true;
     }
     return false;
 }
}

这道题要知道将其视为一维数组，并且根据mid要知道此时是多少行、多少列。
matrix[mid / cols][mid % cols]

LeetCode 278 第一个错误版本

public class Solution extends VersionControl {
 // 这道题实在没啥说的，就这样
 public int firstBadVersion(int n) {
     int start = 1, end = n;
     while (start + 1 < end) {
         int mid = start + (end - start) / 2;
         if (isBadVersion(mid)) {
             end = mid;
         } else {
             start = mid;
         }
     }
     // 最后范围收缩到两个，寻找第一个
     if (isBadVersion(start)) {
         return start;
     }
     return end;
 }
}

刷题第二站非升序数组

这里的二分搜索就稍微有些变形。但大体还是给你一个数组(只是不是完好的升序了)。
下面这些题要分清情况，不要遗漏，否则，肯定有实例不会童年过。尤其是第三、第四两题，即旋转数组(含重复元素)。

LeetCode 162 寻找峰值

这道题我只能说比较难，但是呢？如果你理解了，我只能说，也不过如此。但是还是要好好体会的。
我们平时做二分法题目都是在一个升序数组中，然后我们根据mid值与target比较，从而确定是去左边、还是右边、还是直接返回mid。
二分法的关键就是一分为二，并且有能力通过一定条件选择向左、向右还是已找到。因此不拘泥于是否是升序数组，这个原本的事务可能是任何东西，当然大底会是一个数组的样子。只要其具有二分后可以选择左右即可。
这道题，我们很明显知道峰值一定存在于答案中。我们寻找到mid后，如果mid就是峰值，此时返回即可(因为不是要找所有峰值，而是任意一个，如果这道题是找所有峰值，不能用二分法，只能遍历)。如果不是峰值，则可能是在一条向下的边上；亦可能是在一条向上的边上；如果是低估，无所谓放在向上或向下边上这种情况讨论。因此分三种情况：
1.中间点正好是峰值，返回
2.中间点在向上的趋势线上，则右侧必有峰值
3.中间点在向下的趋势线上，则左侧必有峰值

class Solution {
 public int findPeakElement(int[] nums) {
     if (nums == null || nums.length == 0) {
         return -1;
     }
     int start = 0, end = nums.length - 1;
     while (start + 1 < end) {
         int mid = start + (end - start) / 2;
         if (mid - 1 >= 0 && mid + 1 < nums.length && nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
             return mid;
         } else if (mid - 1 >= 0 && nums[mid - 1] > nums[mid]) { // 在下降趋势
             end = mid;
         } else if (mid + 1 <nums.length && nums[mid + 1] > nums[mid]) { // 在上升趋势
             start = mid;
         }
     }

     // 此时剩下两个元素
     if (nums[start] >= nums[end]) { // 其实当等于时，是考虑到该数组本来就只有一个元素
         return start;
     }
     return end;
 }
}

LeetCode 33 搜索旋转排序数组

这道题好好看看，我写了好多遍才对

public class Solution {
 public int search(int[] A, int target) {
     if (A == null || A.length == 0) {
         return -1;
     }

     int start = 0;
     int end = A.length - 1;
     int mid;

     while (start + 1 < end) {
         mid = start + (end - start) / 2;
         if (A[mid] == target) {
             return mid;
         }
         if (A[start] < A[mid]) {
             // situation 1, red line
             if (A[start] <= target && target <= A[mid]) {
                 end = mid;
             } else {
                 start = mid;
             }
         } else {
             // situation 2, green line
             if (A[mid] <= target && target <= A[end]) {
                 start = mid;
             } else {
                 end = mid;
             }
         }
     } // while

     if (A[start] == target) {
         return start;
     }
     if (A[end] == target) {
         return end;
     }
     return -1;
 }
}

LeetCode 81 搜索旋转排序数组II

class Solution {
 public boolean search(int[] nums, int target) {
     if (nums == null || nums.length == 0) {
         return false;
     }
     int start = 0, end = nums.length - 1;
     while (start + 1 < end) {
         int mid = start + (end - start) / 2;
         if (nums[mid] == target) {
             return true;
         }

         if (nums[mid] > nums[start]) { // 在左侧
             if (target >= nums[start] && target <= nums[mid]) {
                 end = mid;
             } else {
                 start = mid;
             }
         } else if (nums[mid] < nums[end]) { // 在右侧
             if (target >= nums[mid] && target <= nums[end]) {
                 start = mid;
             } else {
                 end = mid;
             }
         } else if (nums[mid] == nums[start]) { // 此时可能在左，也可能在右
             start++;
         } else if (nums[mid] == nums[end]) {  // 此时可能在左，也可能在右
             end--;
         }
     }
     if (nums[start] == target || nums[end] == target) {
         return true;
     }
     return false;
 }
}

LeetCode 153 寻找旋转排序数组中的最小值

class Solution {
 public int findMin(int[] nums) {
     if (nums == null || nums.length == 0) {
         throw new RuntimeException("数组异常");
     }

     int start = 0, end = nums.length - 1;

     // 判断特殊情况
     if (nums[start] < nums[end]) {
         return nums[start];
     }

     while(start + 1 < end) {
         int mid = start + (end - start) / 2;
         if (nums[mid] >= nums[start]) { // mid点在左侧,则此时最小值在右侧
             start = mid;
         } else {
             end = mid;
         }
     }

     return Math.min(nums[start], nums[end]);
 }
}

LeetCode 154 寻找旋转排序数组中的最小值II

这道题好磨我一会。

class Solution {
 public int findMin(int[] nums) {
     if (nums == null || nums.length == 0) {
         throw new RuntimeException("数组异常");
     }
     int start = 0, end = nums.length - 1;
     // 特殊判断  非降序数组
     /*if (nums[start] < nums[end]) {
         return nums[start];
     }*/
     while (start + 1 < end) {
         // 每次循环都做这个判断一次
         if (nums[start] < nums[end]) {
             return nums[start];
         }

         int mid = start + (end - start) / 2;
         if (nums[mid] > nums[start]) { // 中点在左侧,最小值一定在右侧
             start = mid;
         } else if (nums[mid] < nums[end]) { // 中点在右侧，最小值一定在左侧
             end = mid;
         } else if (nums[mid] == nums[start]) {
             start++;
         } else if (nums[mid] == nums[end]) {
             end--;
         }
     }
     return Math.min(nums[start], nums[end]);
 }
}

刷题第N站其他

这里的题也是二分查找，只是一些奇技淫巧，见多了，就不奇怪了。

LeetCode 240 搜索二维矩阵II

class Solution {
 // 从右上角或者左下角开始查找  此处选右上角
 public boolean searchMatrix(int[][] matrix, int target) {
     if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
         return false;
     }
     int rows = matrix.length, cols = matrix[0].length;
     int row = 0, col = cols  - 1;
     // 这个查找过程只会向左，或者向下
     while (col >= 0 && row < rows) {
         if (matrix[row][col] == target) {
             return true;
         } else if (matrix[row][col] > target) {
             col--;
         } else {
             row++;
         }
     }
     return false;
 }
}

滑动窗口——初见

为什么说初见，是因为滑动窗口是一个很重要的概念，海油许多相关概念和题目会设计，但是这里的题目仅涉及简单的概念。
窗口概念
1.L和R不能回退；2.L不能超过R
初始化情况下，L和R=-1；这是窗口中是没有任何数据的。
如何添加数？
R向右移动一下，即添加一个数。
如何减少数？
L向右移动一下即减少一个数。
窗口中的数包含R指向的值，不包含L指向的值，里面含有数的数量是R - L。

刷题第一站滑动窗口概念

LeetCode 209 长队最小的子数组

这道题暴力解法是O(N2)。略。

其中窗口中包含L~R的元素，L不包含，R包含。
sum是始终维护着窗口中元素的和。
循环中每一层都是新的窗口，对于这个窗口要判断和的取向：
1.≥，则更新count并L++；
2.<，则R++
但是这个要看情况，因为R可能已经来到最右端了，如果已经是最右端，那么R已经不能移动了，而要break。为什么break，因为此时窗口中和小于target，即使让L++，依然是小的。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int L = -1;
        int R = 0;
        int count = Integer.MAX_VALUE;
        int sum = nums[0]; // 用于记录窗口中元素的和
        while (L < R) {
            if (sum >= target) {
                count = Math.min(count, R - L);
                L++;
                sum -= nums[L];
            } else {
                if (R != nums.length - 1) {
                    R++;
                    sum += nums[R];
                } else {
                    break;
                }

            }
        }
        return count == Integer.MAX_VALUE ? 0 : count;
    }
}

这里初始化窗口时让其本来就包含一个元素，这样是为了更好的写代码。因为这样每次到这个循环都是一个新的窗口等待去验证和判断。
不然的话，每次在循环中要创建新的窗口，对于新的窗口，要么是R++，要么是L++。这样比较麻烦，当然其实也不麻烦，就看原有sum，如果原有sum窗口本来无元素代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int L = -1;
        int R = -1;
        int count = Integer.MAX_VALUE;
        int sum = 0; // 窗口之和
        while (R < nums.length) { //这个判断条件和上面不同，暂时我还不清楚这里该怎么写合适
            if (sum >= target) {
                count = Math.min(count, R - L);
                L++; // 形成新窗口
                sum -= nums[L];
            } else {
                if (R < nums.length - 1) {
                    R++; // 形成新窗口
                    sum += nums[R];
                } else {
                    break;
                }
            }
        }
        return count == Integer.MAX_VALUE ? 0 : count;
    }
}

接下来就开始介绍数组操作中另一个重要的方法：「滑动窗口」。所谓滑动窗口，「就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果」。滑动窗口的另一种解释：看了可能会领悟到其它一些链接

过程抽象

刷题第一站过程抽象

化抽象为具体，化整为零。

LeetCode

面试题 01.07. 旋转矩阵

class Solution {
    public void rotate(int[][] matrix) {
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix.length - 1;
        while (tR < dR) {
            rotateEdge(matrix, tR++, tC++, dR--, dC--);
        }
    }
    // 给你一个矩阵，和这个矩阵的左上角和右下角，你会旋转吗？
    private void rotateEdge(int[][] matrix, int tR, int tC, int dR, int dC) {
        int times = dC - tC;
        for (int i = 0; i < times; i++) {
            int temp = matrix[tR][tC + i];
            matrix[tR][tC + i] = matrix[dR - i][tC];
            matrix[dR - i][tC] = matrix[dR][dC - i];
            matrix[dR][dC - i] = matrix[tR + i][dC];
            matrix[tR + i][dC] = temp;
        }
    }
}

剑指 Offer 29. 顺时针打印矩阵

是左神的代码，很经典，可以看一下

public void printEdge(int[][] m, int tR, int tC, int dR, int dC) {
    if (tR = dR) {
        for (int i = tC; i <= dC; i++) {
            System.out.print(m[tR][i] + " ");
        }
    } else if (tC == dC) {
        for (int i = tR; i <= dR; i++) {
            System.out.print(m[i][tC] + " ");
        }
    } else {
        int curC = tC;
        int curR = tR;
        while (curC != dC) {
            System.out.print(m[tR][curC] + " ");
            curC++;
        }
        while (curR != dR) {
            System.out.print(m[tR][curC] + " ");
            curR++;
        }
        while (curC != tC) {
            System.out.println(m[dR][curC] + " ");
            curC--;
        }
        while (curR != tR) {
            System.out.print(m[curR][tC] + " ");
            curR--;
        }
    }
}

那么主程序就非常简单了

public void spiralOrderPrint(int[][] matrix) {
    int tR = 0;
    int tC = 0;
    int dR = matrix.length - 1;
    int dC = matrix[0].length - 1;
    while (tR <= dR && tC <= dC) {
        printEdge(matrix, tR++, tC++, dR--, dC--);
    }
}

54. 螺旋矩阵

循环中是解决一圈，然后在末尾位置换到下一圈。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while (tR <= dR && tC <= dC) {
            // 如果只有一行
            if (tR == dR) {
                for (int i = tC; i <= dC; i++) {
                    list.add(matrix[tR][i]);
                }
            } else if (tC == dC) { // 如果只有一列
                for (int i = tR; i <= dR; i++) {
                    list.add(matrix[i][tC]);
                }
            } else { // 既不是一行，也不是一列
                for (int i = tC; i < dC; i++) {
                    list.add(matrix[tR][i]); // left to right.
                }
                for (int i = tR; i < dR; i++) {
                    list.add(matrix[i][dC]); // top to bottom.
                }
                for (int i = dC; i > tC; i--) {
                    list.add(matrix[dR][i]);
                }
                for (int i = dR; i > tR; i--) {
                    list.add(matrix[i][tC]);
                }
            }
            tR++; // 这一行已经结束，换下一行
            dC--; // 这一列结束，左移一列
            dR--; // 这一行结束，上移一行
            tC++; // 这一列结束，右移一列
        }
        return list;
    }
}

59. 螺旋矩阵 II

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int tR = 0;
        int tC = 0;
        int dR = n - 1;
        int dC = n - 1;
        int index = 1; // 指定当前处理位置要放置的元素，没处理一个位置就++
        while (tR <= dR) {
            if (tR == dR) { // 如果只剩下一行且一列，即最后一个中心元素。这种情况，当n为奇数时会发生
                matrix[tR][tC] = index;
            } else {// 不止一行和一列
                for (int i = tC; i < dC; i++) { // from left to right
                    matrix[tR][i] = index++;
                }
                for (int i = tR; i < dR; i++) {
                    matrix[i][dC] = index++; // from top to botton
                }
                for (int i = dC; i > tC; i--) {
                    matrix[dR][i] = index++; // from right to left
                }
                for (int i = dR; i > tR; i--) {
                    matrix[i][tC] = index++; // from botton to top
                }
            }
            tR++;
            tC++;
            dR--;
            dC--;
        }
        return matrix;
    }
}

总结

数组是非常基础的数据结构，在面试中，考察数组的题目一般在思维上都不难，主要是考察对代码的掌控能力
也就是说，想法很简单，但实现起来可能就不是那么回事了。
首先要知道数组在内存中的存储方式，这样才能真正理解数组相关的面试题
「数组是存放在连续内存空间上的相同类型数据的集合。」
数组可以方便的通过下表索引的方式获取到下表下对应的数据。
需要两点注意的是

「数组下表都是从0开始的。」
「数组内存空间的地址是连续的」

正是「因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。」

经典题目

在面试中，数组是必考的基础数据结构。
其实数据的题目在思想上一般比较简单的，但是如果想高效，并不容易。
我们之前一共讲解了四道经典数组题目，每一道题目都代表一个类型，一种思想。
类型一：二分法
这道题目呢，考察的数据的基本操作，思路很简单，但是在通过率在简单题里并不高，不要轻敌。
可以使用暴力解法，通过这道题目，如果要求更优的算法，建议试一试用二分法，来解决这道题目
暴力解法时间复杂度：O(n)
二分法时间复杂度：O(logn)
在这道题目中我们讲到了「循环不变量原则」，只有在循环中坚持对区间的定义，才能清楚的把握循环中的各种细节。
「二分法是算法面试中的常考题，建议通过这道题目，锻炼自己手撕二分的能力」。
类型二：双指针法
双指针法（快慢指针法）：「通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。」
暴力解法时间复杂度：O(n^2)
双指针时间复杂度：O(n)
这道题目迷惑了不少同学，纠结于数组中的元素为什么不能删除，主要是因为以下两点：

数组在内存中是连续的地址空间，不能释放单一元素，如果要释放，就是全释放（程序运行结束，回收内存栈空间）。
C++中vector和array的区别一定要弄清楚，vector的底层实现是array，所以vector展现出友好的一些都是因为经过包装了。

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法。
类型三：滑动窗口
本题介绍了数组操作中的另一个重要思想：滑动窗口。
暴力解法时间复杂度：O(n^2)
滑动窗口时间复杂度：O(n)
本题中，主要要理解滑动窗口如何移动窗口起始位置，达到动态更新窗口大小的，从而得出长度最小的符合条件的长度。
「滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。」
如果没有接触过这一类的方法，很难想到类似的解题思路，滑动窗口方法还是很巧妙的。
类型四：模拟行为
模拟类的题目在数组中很常见，不涉及到什么算法，就是单纯的模拟，十分考察大家对代码的掌控能力。
在这道题目中，我们再一次介绍到了「循环不变量原则」，其实这也是写程序中的重要原则。
相信大家又遇到过这种情况：感觉题目的边界调节超多，一波接着一波的判断，找边界，踩了东墙补西墙，好不容易运行通过了，代码写的十分冗余，毫无章法，其实「真正解决题目的代码都是简洁的，或者有原则性的」，大家可以在这道题目中体会到这一点。

数组

理论

思维导图

子数组问题

刷题第一站

矩阵问题

刷题第一站

O(n)类型问题

刷题第一站

双指针

刷题第一站

LeetCode 27 移除元素

LeetCode 26 删除有序数组中的重复项

LeetCode 15 三数之和

LeetCode 18 四数之和

链表

分治

刷题第一站

哈希法

刷题第一站 hasMap

LeetCcode 1 两数之和

LeetCode 454 四数相加 II

二分法

刷题第一站 first or last

LeetCode 704 二分查找

LeetCode 35 搜索插入位置

LeetCode 74 搜索二维矩阵

LeetCode 278 第一个错误版本

刷题第二站 非升序数组

LeetCode 162 寻找峰值

LeetCode 33 搜索旋转排序数组

LeetCode 81 搜索旋转排序数组II

LeetCode 153 寻找旋转排序数组中的最小值

LeetCode 154 寻找旋转排序数组中的最小值II

刷题第N站 其他

LeetCode 240 搜索二维矩阵II

滑动窗口——初见

刷题第一站 滑动窗口概念

LeetCode 209 长队最小的子数组

过程抽象

刷题第一站 过程抽象

LeetCode

总结

经典题目

刷题第二站非升序数组

刷题第N站其他

刷题第一站滑动窗口概念

刷题第一站过程抽象