33.日常算法

1.螺旋矩阵

题目来源
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<vector<int>> dis = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        vector<vector<bool>> vis(matrix.size(), vector<bool>(matrix[0].size(), false));
        int diction = 0;
        int total = matrix.size() * matrix[0].size();
        vector<int> ret(total);
        int row = 0, col = 0;
        int idx = 0;
        for (int i = 0; i < total; ++i){
            ret[i] = matrix[row][col];
            vis[row][col] = true;
            int newrow = row + dis[idx][0], newcol = col + dis[idx][1];
            if (newrow >= matrix.size() || newcol >= matrix[0].size() || vis[newrow][newcol]){
                ++idx;
                idx %= 4;
            }
            row = row + dis[idx][0];
            col = col + dis[idx][1];
        }
        return ret;
    }
};

2. 和为 K 的子数组

题目来源
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1; // 进行初始化
        int sum = 0;
        int ret = 0;
        for (auto & x : nums){
            sum += x;
            if (hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};