电脑坏了加上忘了，鸽了有点久。正好今天有空，就好好复习复习。

力扣

560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

解答

构造前缀和数组pre[]，我们可以将题目条件“翻译”，寻找子数组$[j..i]$和为$k$即为$pre[i] - pre[j - 1] == k$，即为$pre[j - 1] == pre[i]- k$。所以我们建立一个hash tablehash_map，存储每个前缀和对应的出现次数。只要找到hash_map[pre-k]的值存在，那么ans += hash_map[pre - k]即可。答案如下：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0, pre = 0;
        unordered_map<int, int> hash_map;
        hash_map.insert({0, 1});
        for (auto &n : nums) {
            pre += n;
            if (hash_map.find(pre - k) != hash_map.end()) {
                ans += hash_map[pre - k];
            }
            hash_map[pre]++;
        }
        return ans;
    }
};

插个题外话，感觉上两周写的垃圾题挺多的，大多没啥价值啊。。

46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

解答

第一次做回溯法确实不太熟练，这周又做了一道也是没能解答。

如何获得全排列呢？将每个元素依次挪到队首，然后针对剩余的元素就是一种排列，然后对其后面的元素递归进行这个操作。维护一个指针first指向操作首元素这样就可以不需要进行数组容量修改的操作。

class Solution {
public:
    void backtrack(vector<vector<int>> &res, vector<int> output, int first, int len) {
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; i++) {
            swap(output[i], output[first]);
            backtrack(res, output, first + 1, len);
            swap(output[i], output[first]);
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        backtrack(ans, nums, 0, nums.size());
        return ans;
    }
};

这题更有意思的是证明为什么结果肯定是全排列。