力扣第35场双周赛

这场比赛是建行赞助的，不得不说，国企就是有钱，已经霸占双周赛两三个月了，貌似还会继续，nb！！！

不多说了，看题：

思路一：直接暴力，枚举所有奇数长度的子数组即可，用O(n^3)的时间复杂度也能过。

代码（copy大佬的C++码）：

 1 class Solution {
 2 public:
 3     int sumOddLengthSubarrays(vector<int>& arr) {
 4 
 5         int res = 0;
 6         for(int i = 0; i < arr.size(); i ++)
 7             for(int sz = 1; i + sz - 1 < arr.size(); sz += 2)
 8                 res += accumulate(arr.begin() + i, arr.begin() + i + sz, 0);
 9 //一个累加求和函数，头两个形参指定要累加的元素范围，第三个形参则是累加的初值
10         return res;
11     }
12 };

View Code

思路二：既然是连续子序列的和，很容易想到前缀和。可以先计算前缀和数组，之后使用O(1)的时间即可计算一个连续子数组的和。总时间复杂度位O（n^2），空间复杂度O（n）。

代码(Java):

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int ans = 0;
        int[] preSum = new int[arr.length +5];
        preSum[0] = arr[0];
        for (int i = 1;i < arr.length; i++)
            preSum[i] = arr[i] + preSum[i-1];
        for (int i = 0;i < arr.length; i++) 
            for (int j = i; j < arr.length; j +=2) {
                if(i == 0)
                    ans += preSum[j];
                else
                    ans += preSum[j] - preSum[i - 1];
            }
        return ans;
    }
}

View Code

思路三：计算所有奇数长度的子数组和--->换成计算每个数字所需要加的次数来得出最终结果。

对于任意元素i(下标)，左边的元素可以一次性取0~i个，共i+1种方案，其中(i+1)/2种为奇数，i/2+1种为偶数；

右边的元素可以一次性取0 ~ n-i-1个，共n-i种方案，其中(n-i)/2种为奇数，(n-i+1)/2种为偶数；

所以左奇+右奇+本身或左偶+右偶+本身即可得到连续奇数组。所以arr[i]出现的次数=左奇*右奇+左偶*右偶。

代码(Java)：

 1 public int sumOddLengthSubarrays(int[] arr) {
 2         int ans = 0;
 3         int l1 = 0,r1 = 0,l2 = 0,r2 = 0;
 4         for (int i = 0; i < arr.length; i++) {
 5             l1 = (i + 1) / 2;
 6             l2 = i / 2 + 1;
 7             r1 = (arr.length - i) / 2;
 8             r2 = (arr.length - i +1) / 2;
 9             ans += (l1*r1+l2*r2) *arr[i];
10         }
11         return ans;
12     }

View Code

2、5505. 所有排列中的最大和

题意：给一个数组，元素顺序可以打乱，根据给出的区间计算所有区间内元素最大和。

思路：这个题跟1题的第三种方法有一丢丢像，我们需要统计每个索引位置的查询次数，然后贪心：数组元素越大，对应越多的查询次数。

怎样根据给出的不同区间统计查询次数：

使用扫描线：对于每一个request[start, end]，从start开始的数字查询次数增加一次，从end+1开始的查询系数减少一次，可以用一个cnt数组，对每一个查询区间，进行cnt[start]++、cnt[end + 1] --；得到的cnt数组的每个元素的前缀和就是这个元素的查询次数。

代码(Java)：

 public int maxSumRangeQuery(int[] nums, int[][] requests) {
        long sum = 0;
        int mod = 1000000007;
        int[] cnt = new int[nums.length + 5];//防止越界数据
        for (int i = 0; i < requests.length; i++) {
            cnt[requests[i][0]]++;
            cnt[requests[i][1]+1]--;
        }
        for (int i = 1; i < nums.length; i++)
            cnt[i] = cnt[i] + cnt[i - 1];
        Arrays.sort(nums);
        Arrays.sort(cnt, 0, nums.length);
        for (int i = nums.length - 1; i >= 0; i--)
            sum = (sum + nums[i] * cnt[i]) % mod;
        return (int)sum;
    }

View Code

3、5504. 使数组和能被 P 整除

题意:将给定数组的一部分移除，使得剩余元素和能被p整除，不能移除全部元素。

思路：

假设 nums 的和除以 P，余数是 mod，
如果 mod == 0，答案就是 0。
如果 mod != 0，答案变成了找原数组中的最短连续子数组，使得其数字和除以 P，余数也是 mod。
由于是求解连续子数组和的问题，很容易想到使用前缀和。
假设当前前缀和除以 P 的余数是 curmod，为了找到一段连续子数组对 P 的余数是 mod，我们需要找到一段前缀和，对 P 的余数是 targetmod。其中 targetmod 的求法是：
如果 curmod >= mod，很简单：targetmod = curmod - mod；
如果 curmod < mod，我们需要加上一个 P：targetmod = curmod - mod + P；
这样，我们可以保证，当前前缀和减去目标前缀和，剩余的数组对 P 的余数是 mod。我们只需要找最短的这样的数组就好。
最后，为了快速找到一段对 P 的余数为 targetmod 的前缀和，我们使用一个哈希表 table，来存储之前前缀和对 P 的余数和所在的索引。（key 为余数；value 为索引）。table 在遍历过程中更新，以保证每次在 table 中查找到的，是离当前元素最近的索引，从而保证找到的是“最短”的连续子数组。

代码：

public int minSubarray(int[] nums, int p) {
        int ans = nums.length;
        long sum = 0;
        for (int i: nums)
            sum += i;
        int mod = (int)(sum % p);
        if (mod == 0)
            return 0;
        HashMap<Integer,Integer> preSum = new HashMap<>();
        preSum.put(0, -1);
        sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int currentMod = (int)(sum % p);
            preSum.put(currentMod, i);
            int tmp = currentMod >= mod ? currentMod - mod:(currentMod + p - mod);
            if(preSum.containsKey(tmp))
                ans = Math.min(ans, i-preSum.get(tmp));
        }
        return ans == nums.length ? -1:ans;
    }

View Code

力扣第35场双周赛

推荐阅读