22.日常算法

1. 按奇偶排序数组

题目来源
给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。
返回满足此条件的 任一数组 作为答案。

示例 1：
输入：nums = [3,1,2,4]
输出：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left != right){
            while (left < right && nums[left] % 2 == 0) left++;
            while (left < right && nums[right] % 2 != 0) right--;
            swap(nums[left], nums[right]);
        }
        return nums;
    }
};

2. 找到字符串中所有字母异位词

题目来源
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。

示例 1：
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的变位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的变位词。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        if (p.size() > s.size()) return ret;
        unordered_map<char, int> hash;
        for (auto & x : p) hash[x]++;
        int left = 0, right = 0, count = 0;
        while (right < s.size()){
            hash[s[right]]--;
            count++;
            while (hash[s[right]] < 0){
                hash[s[left++]]++;
                --count;
            }
            if (count == p.size()) ret.push_back(left);
            ++right;
        }
        return ret;
    }
};