@ninijia 在 Leetcode每日一题练习 ------ 1524. 和为奇数的子数组数目 中发帖
从Leetcode 每日一题练习继续讨论:
1524. 和为奇数的子数组数目
1524. Number of Sub-arrays With Odd Sum
题解
本题注意题目要求仅需要判断子数组和的奇偶性,并不要求得到子数组和的具体数值,因此要从奇偶性的特点出发,寻找可以简化解题过程的方法。
如果仅考虑计算得到子数组和的情况下,每次向后遍历新的数字时只需将新数字和以前一个数字为结尾的后缀和数组依次相加即得到新的子数组和,即当前数字下标为n+1的情况下,只需将数字分别和n,n+n-1,n+n-1+n-2…相加即得以n+1结尾的子数组和,但由于题目不要求得到子数组和的具体数值,只要求得到奇偶性,因此可以将计算具体的子数组和简化为仅分别记录以n+1结尾的子数组中子数组和为奇数和偶数的个数。根据奇数与奇数相加得到偶数,偶数与奇数相加得到奇数的规则,若n+1对应的数字为奇数,则将n对应的奇...