抱佛脚一时爽，一直抱佛脚一直爽！这篇文章总结常见的数组问题~
参考链接：leetcode 剑指offer

挪元素的题目

旋转数组（lc189）

法一：使用辅助数组

void rotate(vector<int>& nums, int k) {
    vector<int> t = nums;
    for (int i = 0; i < nums.size(); ++i) {
        nums[(i + k) % nums.size()] = t[i];
    }
}

法二：先把前 n-k 个数字翻转一下，再把后k个数字翻转一下，最后再把整个数组翻转一下
法三：从数组的末尾取k个数组放入数组的开头

void rotate(vector<int>& nums, int k) {
    if (nums.empty() || (k %= nums.size()) == 0) return;
    int n = nums.size();
    for (int i = 0; i < n - k; ++i) {
        nums.push_back(nums[0]);
        nums.erase(nums.begin());
    }
}

把奇数挪到前面+保持原有相对顺序（jz13）

void reOrderArray(vector<int> &array) {
        int n = array.size();
        if (n <= 1) return;
        int i = 0;
        while (i < n) {
            while (i < n && array[i] % 2 == 1) ++i; // 找到第一个偶数
            if (i >= n - 1) break;
            int j = i + 1
            while (j < n && array[j] % 2) ++j; // 找到array[i]之后的第一个奇数
            if (j >= n) break;
            int odd = array[j];
            array.erase(array.begin() + j);
            array.insert(array.begin() + i, odd);
            ++i;
        }
}

把0挪到后面+保持原有顺序（lc283）

注意：要实时更新长度：--n

void moveZeroes(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return;
        int i = 0;
        while (i < n) {
          while (i < n && nums[i] != 0) ++i;
          if (i == n) break;
          nums.erase(nums.begin() + i);
          nums.push_back(0);
          --n;
        }
}

把奇数挪到前面+无需保持原有顺序

思路：双指针

    bool changeArray(int *a, int size) {
        if(size <= 0)
            return false;
        int beg = 0, end = size -1;
        while(beg < end) {
            while(beg < end && IsOdd(a[beg]))
                ++beg;
            while(beg < end && !IsOdd(a[end]))
                --end;
            if(beg < end) {
                int tmp = a[beg];
                a[beg] = a[end];
                a[end] = tmp;
            }
        }
        return true;
    }

根据身高重建队列（lc406）

法一：先按v[0]从大到小、v[1]从小到大排序；每次取出一个，插入到result的v[1]位置处

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    auto cmp = [](vector<int>& v1, vector<int>& v2) {
        if (v1[0] == v2[0]) return v1[1] < v2[1];
        else return v1[0] > v2[0];
    };
    sort(people.begin(), people.end(), cmp);
    vector<vector<int>> result;
    for (auto v : people) {
        int index = v[1];
        result.insert(result.begin() + index, v);
    }
    return result;
}

法二：思路与法一类似，但不使用额外空间

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    sort(people.begin(), people.end(), [](vector<int>& a, vector<int>& b) {
        return a[0] > b[0] || (a[0] == b[0] && a[1] < b[1]);
    });
    for (int i = 0; i < people.size(); i++) {
        auto p = people[i];
        if (p[1] != i) {
            people.erase(people.begin() + i);
            people.insert(people.begin() + p[1], p);
        }
    }
    return people;
}

子数组/子序列的题目

连续子数组最大和（jz30）

法一：dp，curSum记录以当前元素结尾的子数组的最大和；curSum = max(curSum + nums[i], nums[i])
法二：分治

int maxSubArray(vector<int>& nums, int left, int right) {
    if (left >= right) return nums[left];
    int mid = left + (right - left) / 2;
    int max_left_sub = maxSubArray(nums, left, mid - 1);
    int max_right_sub = maxSubArray(nums, mid + 1, right);
    int max_left = 0, max_right = 0;
    int sum_left = 0, sum_right = 0;
    for (int i = mid - 1; i >= left; --i) {
        sum_left += nums[i];
        max_left = max(max_left, sum_left);
    }
    for (int i = mid + 1; i <= right; ++i) {
        sum_right += nums[i];
        max_right = max(max_right, sum_right);
    }
    return max(max_left_sub, max(max_right_sub, max_left + nums[mid] + max_right));
}

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if (!n) return 0;
    return maxSubArray(nums, 0, n - 1);
}

连续子数组最大积（lc152）

思路：
1. f[i] 表示子数组 [0, i] 范围内并且一定包含 nums[i] 数字的最大子数组乘积
2. g[i] 表示子数组 [0, i] 范围内并且一定包含 nums[i] 数字的最小子数组乘积
3. 此时的最大值和最小值只会在这三个数字之间产生，即 f[i-1]*nums[i]，g[i-1]*nums[i]，和 nums[i]

int maxProduct(vector<int>& nums) {
    int n = nums.size();
    if (!n) return 0;
    int res = nums[0], curMin = num[0], curMax = nums[0];
    for (int i = 1; i < n; ++i) {
        int tmpMin = min(min(curMin * nums[i], curMax * nums[i]), nums[i]);
        int tmpMax = max(max(curMin * nums[i], curMax * nums[i]), nums[i]);
        curMin = tmpMin;
        curMax = tmpMax;
        res = max(res, curMax);
    }
    return res;
}

和为s的连续正整数序列（jz41）

思路：双指针

和>=target的长度最小的子数组（lc209）

法一：和无重复字符的最大子串类似，双指针

int minSubArrayLen(int s, vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total < s) return 0;
    if (total == s) return nums.size();
    int left = 0, right = 0, curSum = nums[0], res = INT_MAX;
    while (right < nums.size()) {
        if (curSum >= s) {
            res = min(res, right - left + 1);
            curSum -= nums[left];
            ++left;
        } else {
            ++right;
        if (right < nums.size()) curSum += nums[right];
        }
    }
    return res;
}

法二：二分法

int minSubArrayLen(int s, vector<int>& nums) {
    int len = nums.size(), sums[len + 1] = {0}, res = len + 1;
    for (int i = 1; i < len + 1; ++i) sums[i] = sums[i - 1] + nums[i - 1];
    for (int i = 0; i < len + 1; ++i) {
        int right = searchRight(i + 1, len, sums[i] + s, sums);
        if (right == len + 1) break;
        if (res > right - i) res = right - i;
    }
    return res == len + 1 ? 0 : res;
} 
int searchRight(int left, int right, int key, int sums[]) {     
    while (left <= right) {
        int mid = (left + right) / 2;
        if (sums[mid] >= key) right = mid - 1;
        else left = mid + 1;
    }
    return left;
}

和为k的子数组个数（lc560）

思路：遍历数组中的数字，用 sum 来记录到当前位置的累加和，查找 sum-k 是否存在，即是否有连续子数组的和为 sum-k；如果存在的话，那么和为k的子数组一定也存在
注意：一定要初始化为{0,1}，以处理sum=k的情况

int subarraySum(vector<int>& nums, int k) {
    int n = nums.size();
    if (!n) return 0;
    int sum = 0, res = 0;
    unordered_map<int, int> m = {{0, 1}}; // 一定要初始化为{0,1}，以处理sum=k的情况
    for (int i = 0; i < n; ++i) {
        sum += nums[i];
        if (m.count(sum - k)) res += m[sum - k];
        if (!m.count(sum)) m[sum] = 0;
        ++m[sum];
    }   
    return res;
}

最长上升子序列（lc300）

法一：原始dp

for (int j = i - 1; j >= 0; j--) {
    if (nums[j] < nums[i]) {
        dp[i] = max(dp[i], dp[j] + 1);
    }
}

法二：二分查找，先建立一个空的 dp 数组，然后开始遍历原数组，对于每一个遍历到的数字，用二分查找法在 dp 数组找第一个不小于它的数字，如果这个数字不存在，那么直接在 dp 数组后面加上遍历到的数字，如果存在，则将这个数字更新为当前遍历到的数字，最后返回 dp 数组的长度即可

最长重复子数列（lc718）

动态规划

int findLength(vector<int>& A, vector<int>& B) {
    int lenA = A.size(), lenB = B.size();
    if (!lenA || !lenB) return 0;
    vector<vector<int>> dp(lenA + 1, vector<int>(lenB + 1, 0));
    int res = 0;
    for (int i = 1; i <= lenA; ++i) {
        for (int j = 1; j <= lenB; ++j) {
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                res = max(res, dp[i][j]);
            }
            else dp[i][j] = 0;
        }
    }
    return res;
}

最长重复子序列（lc1143）

int longestCommonSubsequence(string text1, string text2) {
    int len1 = text1.size(), len2 = text2.size();
    vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
    for (int i = 1; i <= len1; ++i) {
        for (int j = 1; j <= len2; ++j) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[len1][len2];
}

最长连续序列（lc128）

int longestConsecutive(vector<int>& nums) {
    int res = 0;
    unordered_set<int> s(nums.begin(), nums.end());
    for (int num : nums) {
        if (!s.count(num)) continue;
        s.erase(num);
        int pre = num - 1, post = num + 1;
        while (s.count(pre)) s.erase(pre--);
        while (s.count(post)) s.erase(post++);
        res = max(res, post - pre - 1);
    }
    return res;
}

重复元素的题目

删除排序数组中重复出现的元素（lc26）

注意：凡是删除重复元素的都可以用这种覆盖的思路！

    int removeDuplicates(vector<int>& nums) {
        int pre = 0, cur = 0, n = nums.size();
        while (cur < n) {
            if (nums[pre] == nums[cur]) ++cur;
            else nums[++pre] = nums[cur++];
        }
        return nums.empty() ? 0 : (pre + 1);
    }

找数组中的众数（jz28）

法一：sort->取中间的数a->从中间向两边搜a出现了多少次->大于一半次数则返回a
法二：

int majorityElement(vector<int>& nums) {
    int res = 0, cnt = 0;
    for (int num : nums) {
        if (cnt == 0) {res = num; ++cnt;}
        else (num == res) ? ++cnt : --cnt;
    }     
    return res;
}

找重复数字（lc287）

法一：二分

int findDuplicate(vector<int>& nums) {
    int left = 1, right = nums.size(); // 这里的left和right并不是nums的index，而是表示区间[1,n]
    while (left < right){
        int mid = left + (right - left) / 2, cnt = 0;
        for (int num : nums) {
            if (num <= mid) ++cnt;
        }
        if (cnt <= mid) left = mid + 1;
        else right = mid; // 因为会令right = mid，所以必须是while (left < right)，否则构成死循环
    }
    return right;
}

法二：用快慢指针找到环的入口

    int findDuplicate(vector<int>& nums) {
        int slow = 0, fast = 0, t = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }
        while (true) {
            slow = nums[slow];
            t = nums[t];
            if (slow == t) break;
        }
        return slow;
    }

找排序数组中给定数字的起始和结束位置（lc34）

    vector<int> searchRange(vector<int>& nums, int target) {
      // 找到nums中第一个不小于target的数
      int left = 0, right = nums.size();
      while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;
      }
      int pos1 = right;
      // 找到nums中第一个大于target的数
      left = 0, right = nums.size();
      while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) left = mid + 1;
        else right = mid;
      }
      int pos2 = right;
      if (pos1 == pos2) return {-1, -1};
      return {pos1, pos2 - 1};
    }

其他题目

搜索旋转排序数组（lc33）

二分搜索法的关键在于获得了中间数后，判断下面要搜索左半段还是右半段
如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1; // right必须是n - 1，不能是n
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] > nums[right]) { // 左半段是有序的
            if (target >= nums[left] && target < nums[mid]) right = mid - 1; // 在左半段搜索target
            else left = mid + 1;
        } else {
            if (target > nums[mid] && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

分发糖果（lc135）

思路：首先初始化每个人一个糖果，然后这个算法需要遍历两遍，第一遍从左向右遍历，如果右边的小盆友的等级高，等加一个糖果，这样保证了一个方向上高等级的糖果多。然后再从右向左遍历一遍，如果相邻两个左边的等级高，而左边的糖果又少的话，则左边糖果数为右边糖果数加一。最后再把所有小盆友的糖果数都加起来返回即可

int candy(vector<int>& ratings) {
    int res = 0, n = ratings.size();
    if (!n) return res;
    vector<int> candies(n, 1);
    for (int i = 0; i < n - 1; ++i) {
        if (ratings[i] < ratings[i + 1]) candies[i + 1] = candies[i] + 1;
    }
    for (int i = n - 1; i > 0; --i) {
        if (ratings[i] < ratings[i - 1]) candies[i - 1] = max(candies[i - 1], candies[i] + 1);
    }
    res = accumulate(candies.begin(), candies.end(), 0);
    return res;
}

前k个高频元素（lc347）

法一：用堆对map排序

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> m;
    priority_queue<pair<int, int>> q;
    vector<int> res;
    for (int num : nums) {
        if (m.count(num) == 0) m[num] = 0;
        ++m[num];
    }
    for (auto iter : m) {
        q.push({iter.second, iter.first});
    }
    while (k--) {
        res.push_back(q.top().second);
        q.pop();
    }
    return res;
}

法二：桶排序

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> m;
    vector<vector<int>> bucket(nums.size() + 1, vector<int>());
    vector<int> res;
    for (int num : nums) {
        if (m.count(num) == 0) m[num] = 0;
        ++m[num];
    }
    for (auto kv : m) {
        bucket[kv.second].push_back(kv.first);
    }
    for (int i = nums.size(); i > 0; --i) {
        for (int j = 0; j < bucket[i].size(); ++j) {
            if (k == 0) break;
            res.push_back(bucket[i][j]);
            --k;
        } 
    }
    return res;
}

寻找局部峰值（lc162）

法一：暴力搜索
- 注意：把整型最小值直接加入到数组中，然后从第二个数字遍历到倒数第二个数字，这样就不会存在越界的可能了
- corner case：原数组中只有一个数字，且是整型最小值，所以对于数组中只有一个数字的情况在开头直接判断一下

int findPeakElement(vector<int>& nums) {
    if (nums.size() == 1) return 0;
    nums.insert(nums.begin(), INT_MIN);
    nums.push_back(INT_MIN);
    for (int i = 1; i < (int)nums.size() - 1; ++i) {
        if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) return i - 1;
    }
    return -1;
}

法二：二分搜索

    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) { // 注意是小于！
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) left = mid + 1;
            else right = mid;
        }
        return right;
    }

搜索插入位置（lc35）

思路：找到第一个不小于target的数的位置；若未找到返回nums.size()
注意：return right < nums.size() ? right : nums.size();

加油站环绕（lc134）

法一：暴力解法

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    for (int i = 0; i < gas.size(); ++i) { // 从i开始
        int myGas = 0, j = i;
        for (; j < i + gas.size(); ++j) {
            int k = j % gas.size();
            myGas += gas[k];
            if (myGas < cost[k]) break;
            myGas -= cost[k];
        }
        if (j == i + gas.size()) return i;
    }
    return -1;
}

法二

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int total = 0, sum = 0, start = 0;
    for (int i = 0; i < gas.size(); ++i) {
        total += gas[i] - cost[i];
        sum += gas[i] - cost[i];
        if (sum < 0) {
            start = i + 1;
            sum = 0;
        }
    }
    return (total < 0) ? -1 : start;
}

求数组交集（lc349）

法一：把num1数字都放入set，再遍历num2判断
法二：把两个数组都排好序，类似merge 数组的指针法
法三：将一个数组排序，然后遍历另一个数组，把遍历到的每个数字在排序号的数组中用二分查找法搜索，如果能找到则放入结果set中
法四：使用STL的set_intersection函数

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end()), res;
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(res, res.begin()));
    return vector<int>(res.begin(), res.end());
}

每日温度（lc739）

把在数组中的位置而不是元素的值放入栈中

vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> res(n, 0);
    stack<int> st;
    for (int i = 0; i < temperatures.size(); ++i) {
        while (!st.empty() && temperatures[i] > temperatures[st.top()]) { // 注意要判断!st.empty()
            auto t = st.top(); st.pop();
            res[t] = i - t;
        }
        st.push(i);
    }
    return res;
}

计算右侧小于当前元素的个数（lc315）

思路：从右向左遍历数组，找到tmp中第一个不小于nums[i]的数的位置，把nums[i]插入该位置

vector<int> countSmaller(vector<int>& nums) {
    vector<int> tmp;
    vector<int> res(nums.size(), 0);
    for (int i = (int)nums.size() - 1; i >= 0; --i) {
        int left = 0, right = tmp.size(); // 找到tmp中第一个不小于nums[i]的数的位置
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tmp[mid] < nums[i]) left = mid + 1;
            else right = mid;
        }
        res[i] = right;
        tmp.insert(tmp.begin() + right, nums[i]);
    }
    return res;
}

滑动窗口最大值（lc239）

法一：双指针；map

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    if (k == 1) return nums;
    int n = nums.size();
    vector<int> res;
    map<int, int> m;
    for (int i = 0; i < k; ++i) {
        ++m[nums[i]];
    }
    res.push_back(m.rbegin()->first);
    for (int i = 1; i <= n - k; ++i) {
        --m[nums[i - 1]];
        if (!m[nums[i - 1]]) m.erase(nums[i - 1]);
        ++m[nums[i + k - 1]];
        res.push_back(m.rbegin()->first);
    }
    return res;
}

法二：双端队列；存index

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    if (k == 1) return nums;
    int n = nums.size();
    vector<int> res;
    map<int, int> m;
    for (int i = 0; i < k; ++i) {
        ++m[nums[i]];
    }
    res.push_back(m.rbegin()->first);
    for (int i = 1; i <= n - k; ++i) {
        --m[nums[i - 1]];
        if (!m[nums[i - 1]]) m.erase(nums[i - 1]);
        ++m[nums[i + k - 1]];
        res.push_back(m.rbegin()->first);
    }
    return res;
}

抱佛脚-刷题系列之数组

抱佛脚-刷题系列之数组

挪元素的题目

旋转数组（lc189）

把奇数挪到前面+保持原有相对顺序（jz13）

把0挪到后面+保持原有顺序（lc283）

把奇数挪到前面+无需保持原有顺序

根据身高重建队列（lc406）

子数组/子序列的题目

连续子数组最大和（jz30）

连续子数组最大积（lc152）

和为s的连续正整数序列（jz41）

和>=target的长度最小的子数组（lc209）

和为k的子数组个数（lc560）

最长上升子序列（lc300）

最长重复子数列（lc718）

最长重复子序列（lc1143）

最长连续序列（lc128）

重复元素的题目

删除排序数组中重复出现的元素（lc26）

找数组中的众数（jz28）

找重复数字（lc287）

找排序数组中给定数字的起始和结束位置（lc34）

其他题目

搜索旋转排序数组（lc33）

分发糖果（lc135）

前k个高频元素（lc347）

寻找局部峰值（lc162）

搜索插入位置（lc35）

加油站环绕（lc134）

求数组交集（lc349）

每日温度（lc739）

计算右侧小于当前元素的个数（lc315）

滑动窗口最大值（lc239）