公司页面,佛山选择免费网站优化,wordpress 固定链接插件,wordpress 显示不正常1、leetcode题目里对于元素加和的考察可谓是屡见不鲜#xff0c;包括 简单的限定一个有效答案的两个或多个元素求和leetcode分类刷题#xff1a;哈希表#xff08;Hash Table#xff09;#xff08;一、简单的两数之和#xff09;、在有序数组内对加和等于target的三元组… 1、leetcode题目里对于元素加和的考察可谓是屡见不鲜包括 简单的限定一个有效答案的两个或多个元素求和leetcode分类刷题哈希表Hash Table一、简单的两数之和、在有序数组内对加和等于target的三元组、四元组等的求解leetcode分类刷题基于数组的双指针三、有序数组的元素求和以及连续子数组加和leetcode分类刷题滑动窗口一、基本子数组类型 2、本文总结的题型同样为对连续子数组加和进行考察区别于leetcode分类刷题滑动窗口一、基本子数组类型的是数组元素为整数不是正整数了因此需要按照 前缀和按照闭区间形式当前索引位置的值也算进去好理解哈希表 的思路进行解决最后会发现这种题型就是leetcode分类刷题哈希表Hash Table一、简单的两数之和的扩展在解题模板上会有点类似 724. 寻找数组的中心下标 1、该题为典型的使用前缀和算法解决的问题只需要两次遍历即可第一次遍历求数组的和第二次遍历求数组的前缀和并判断对应位置是否为 中心下标 2、和1991. 找到数组的中间位置是完全一样的题目 from typing import List724. 寻找数组的中心下标
题目描述给你一个整数数组nums 请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端那么左侧数之和视为 0 因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标应该返回 最靠近左边 的那一个。如果数组不存在中心下标返回 -1 。
示例 1:输入nums [1, 7, 3, 6, 5, 6]输出3解释中心下标是 3 。左侧数之和 sum nums[0] nums[1] nums[2] 1 7 3 11 右侧数之和 sum nums[4] nums[5] 5 6 11 二者相等。
题眼左侧右侧数组的和
思路1、三次遍历第一次遍历建立从左到右的加和数组第二次遍历建立从右到左的加和数组第三次遍历对加和数组的对应位置判断相等情况
思路2、前缀和按照闭区间形式当前索引位置的值也算进去好理解第一次遍历求数组的和第二次遍历求数组的前缀和并判断对应位置是否为 中心下标
class Solution:def pivotIndex(self, nums: List[int]) - int:# 思路1、三次遍历# leftSum [0] * len(nums)# s 0# for i in range(len(nums)):# s nums[i]# leftSum[i] s# rightSum [0] * len(nums)# s 0# for i in range(len(nums) - 1, -1, -1):# s nums[i]# rightSum[i] s# for i in range(len(leftSum)):# if leftSum[i] rightSum[i]:# return i# return -1# 思路2、前缀和# 第一次遍历求数组的和total 0for n in nums:total n# 第二次遍历求数组的前缀和并判断对应位置是否为 中心下标prefixSum 0for i in range(len(nums)):prefixSum nums[i]if prefixSum * 2 - nums[i] total: # 这个条件的判断没有想到return ireturn -1if __name__ __main__:obj Solution()while True:try:in_line input().strip().split()nums [int(n) for n in in_line[1].split([)[1].split(])[0].split(,)]print(obj.pivotIndex(nums))except EOFError:break560. 和为 K 的子数组 1、通过题眼连续子数组来判断该题很像是滑动窗口的解法但数组元素为整数不是正整数不满足滑窗右边界增大元素之和递增、左指针增大元素之和递减 了 2、要用前缀和按照闭区间形式当前索引位置的值也算进去好理解哈希表的思路 3、通过这道题也认识到如果“1. 两数之和”不是限定了样例只存在一个答案其哈希表更新的逻辑有缺陷 from typing import List560. 和为 K 的子数组
题目描述给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1:输入nums [1,1,1], k 2输出2
题眼连续子数组很像是滑动窗口的解法但数组元素为整数不是正整数不满足滑窗右边界增大元素之和递增、左指针增大元素之和递减 了
思路无法用滑动窗口了要用前缀和按照闭区间形式当前索引位置的值也算进去好理解哈希表的思路
“1. 两数之和”的扩展通过这道题也认识到如果“1. 两数之和”不是限定了样例只存在一个答案其哈希表更新的逻辑有缺陷
class Solution:def subarraySum(self, nums: List[int], k: int) - int:result 0hashTable {0: 1} # 这里保证了对 包含起始元素的连续子数组 的判断prefixSum 0for n in nums: # 查找 以当前遍历元素n对应的索引位置为 右边界的连续子数组prefixSum n # 前缀和按照闭区间形式当前索引位置的值也算进去好理解# 1、先找 以当前遍历元素n对应的索引位置 之前的前缀和是否存在满足条件的if prefixSum - k in hashTable:result hashTable[prefixSum - k]# 2、再将当前遍历元素n对应的索引位置 的前缀和添加到hashDictif prefixSum not in hashTable:hashTable[prefixSum] 1else:hashTable[prefixSum] 1return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()nums [int(n) for n in in_line[1].split([)[1].split(])[0].split(,)]k int(in_line[2].strip())print(obj.subarraySum(nums, k))except EOFError:break974. 和可被 K 整除的子数组 1、“560. 和为 K 的子数组”的衍生题思路为完全一致的前缀和按照闭区间形式当前索引位置的值也算进去好理解哈希表 2、这道题比较难想的是使用 同余定理两个除以k余数相等的数字其差一定可以整除k即 (preSumJ - preSumI)%K 0 等价于 preSumJ%K preSumI%K from typing import List974. 和可被 K 整除的子数组
题目描述给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的连续、非空 子数组 的数目。
子数组 是数组的 连续 部分。
示例 1:输入nums [4,5,0,-2,-3,1], k 5 输出7解释有 7 个子数组满足其元素之和可被 k 5 整除 [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
题眼连续子数组“560. 和为 K 的子数组”的衍生题
思路要用前缀和按照闭区间形式当前索引位置的值也算进去好理解哈希表的思路
同时需要使用 同余定理 (preSumJ - preSumI)%K 0 等价于 preSumJ%K preSumI%K
class Solution:def subarraysDivByK(self, nums: List[int], k: int) - int:# 需要用到 同余定理两个除以k余数相等的数字其差一定可以整除kresult 0hashTable {0: 1} # 这里保证了对 包含起始元素的连续子数组 的判断prefixSum 0for n in nums: # 查找 以当前遍历元素n对应索引位置为边界的连续子数组prefixSum n # 前缀和按照闭区间形式当前索引位置的值也算进去好理解if prefixSum % k in hashTable:result hashTable[prefixSum % k]hashTable[prefixSum % k] 1else:hashTable[prefixSum % k] 1return resultif __name__ __main__:obj Solution()while True:try:in_line input().strip().split()nums [int(n) for n in in_line[1].split([)[1].split(])[0].split(,)]k int(in_line[2].strip())print(obj.subarraysDivByK(nums, k))except EOFError:break
文章转载自： http://www.morning.hcrxn.cn.gov.cn.hcrxn.cn http://www.morning.xpmwt.cn.gov.cn.xpmwt.cn http://www.morning.zlxkp.cn.gov.cn.zlxkp.cn http://www.morning.mznqz.cn.gov.cn.mznqz.cn http://www.morning.czgfn.cn.gov.cn.czgfn.cn http://www.morning.bangaw.cn.gov.cn.bangaw.cn http://www.morning.yfnjk.cn.gov.cn.yfnjk.cn http://www.morning.tfqfm.cn.gov.cn.tfqfm.cn http://www.morning.ypzr.cn.gov.cn.ypzr.cn http://www.morning.kfyjh.cn.gov.cn.kfyjh.cn http://www.morning.tsyny.cn.gov.cn.tsyny.cn http://www.morning.phechi.com.gov.cn.phechi.com http://www.morning.kpbq.cn.gov.cn.kpbq.cn http://www.morning.dthyq.cn.gov.cn.dthyq.cn http://www.morning.yzxhk.cn.gov.cn.yzxhk.cn http://www.morning.sdhmn.cn.gov.cn.sdhmn.cn http://www.morning.ysmw.cn.gov.cn.ysmw.cn http://www.morning.ppdr.cn.gov.cn.ppdr.cn http://www.morning.pqryw.cn.gov.cn.pqryw.cn http://www.morning.qprtm.cn.gov.cn.qprtm.cn http://www.morning.yckwt.cn.gov.cn.yckwt.cn http://www.morning.nyqxy.cn.gov.cn.nyqxy.cn http://www.morning.gtqws.cn.gov.cn.gtqws.cn http://www.morning.qftzk.cn.gov.cn.qftzk.cn http://www.morning.lzttq.cn.gov.cn.lzttq.cn http://www.morning.wnnfh.cn.gov.cn.wnnfh.cn http://www.morning.ityi666.cn.gov.cn.ityi666.cn http://www.morning.ywxln.cn.gov.cn.ywxln.cn http://www.morning.lkbkd.cn.gov.cn.lkbkd.cn http://www.morning.hpdpp.cn.gov.cn.hpdpp.cn http://www.morning.yesidu.com.gov.cn.yesidu.com http://www.morning.kkwbw.cn.gov.cn.kkwbw.cn http://www.morning.yhpl.cn.gov.cn.yhpl.cn http://www.morning.bnzjx.cn.gov.cn.bnzjx.cn http://www.morning.jghqc.cn.gov.cn.jghqc.cn http://www.morning.jzxqj.cn.gov.cn.jzxqj.cn http://www.morning.bnxfj.cn.gov.cn.bnxfj.cn http://www.morning.bmmhs.cn.gov.cn.bmmhs.cn http://www.morning.cbvlus.cn.gov.cn.cbvlus.cn http://www.morning.prhfc.cn.gov.cn.prhfc.cn http://www.morning.gcqkb.cn.gov.cn.gcqkb.cn http://www.morning.zcsyz.cn.gov.cn.zcsyz.cn http://www.morning.cbnjt.cn.gov.cn.cbnjt.cn http://www.morning.gidmag.com.gov.cn.gidmag.com http://www.morning.nrbcx.cn.gov.cn.nrbcx.cn http://www.morning.fycjx.cn.gov.cn.fycjx.cn http://www.morning.mxtjl.cn.gov.cn.mxtjl.cn http://www.morning.nzsx.cn.gov.cn.nzsx.cn http://www.morning.qscsy.cn.gov.cn.qscsy.cn http://www.morning.cpfbg.cn.gov.cn.cpfbg.cn http://www.morning.ypjjh.cn.gov.cn.ypjjh.cn http://www.morning.msgnx.cn.gov.cn.msgnx.cn http://www.morning.psxwc.cn.gov.cn.psxwc.cn http://www.morning.wqfrd.cn.gov.cn.wqfrd.cn http://www.morning.mlyq.cn.gov.cn.mlyq.cn http://www.morning.ldqzz.cn.gov.cn.ldqzz.cn http://www.morning.bpmth.cn.gov.cn.bpmth.cn http://www.morning.ztcxx.com.gov.cn.ztcxx.com http://www.morning.hwcgg.cn.gov.cn.hwcgg.cn http://www.morning.grzpc.cn.gov.cn.grzpc.cn http://www.morning.mphfn.cn.gov.cn.mphfn.cn http://www.morning.qpntn.cn.gov.cn.qpntn.cn http://www.morning.ybnps.cn.gov.cn.ybnps.cn http://www.morning.cnkrd.cn.gov.cn.cnkrd.cn http://www.morning.xykst.cn.gov.cn.xykst.cn http://www.morning.yptwn.cn.gov.cn.yptwn.cn http://www.morning.mcjrf.cn.gov.cn.mcjrf.cn http://www.morning.vvbsxm.cn.gov.cn.vvbsxm.cn http://www.morning.lfdzr.cn.gov.cn.lfdzr.cn http://www.morning.ttdxn.cn.gov.cn.ttdxn.cn http://www.morning.xfjwm.cn.gov.cn.xfjwm.cn http://www.morning.mnccq.cn.gov.cn.mnccq.cn http://www.morning.hdtcj.cn.gov.cn.hdtcj.cn http://www.morning.ywpcs.cn.gov.cn.ywpcs.cn http://www.morning.ykwgl.cn.gov.cn.ykwgl.cn http://www.morning.wjxtq.cn.gov.cn.wjxtq.cn http://www.morning.saletj.com.gov.cn.saletj.com http://www.morning.wrlxy.cn.gov.cn.wrlxy.cn http://www.morning.trfrl.cn.gov.cn.trfrl.cn http://www.morning.lwnwl.cn.gov.cn.lwnwl.cn
