当前位置 博文首页 > Tiger数学之家的博客：LeetCode & 剑指Offer --子数组系列：
给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
示例 1:
输入: [23,2,4,6,7], k = 6
输出: True
解释: [2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2:
输入: [23,2,6,4,7], k = 6
输出: True
解释: [23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
连续子数组和为k的倍数，可以对前缀和 sum 进行取余，取余之后的 sum 必然小于k，此时若在当前位置之前存在一个前缀和等于 sum的情况，则说明两个位置中间的和必为 0 同时也一定是 k的倍数，由此将问题转化为是否存在连续子数组和为 0 的问题。
sum 保存到当前位置 i 的前缀和，mp:map<int, int> 保存 <前缀和对k的取余, 第一次出现 sum%k 的位置>
每次对sum取余，判断在位置 i之前是否存在位置使得前缀和取余后也等于 sum%k 如存在，且位置之差>1（至少有两个数）则返回true
如果一直遍历完，说明不符合条件，返回false
注意:
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
map<int, int> mp;
mp[0] = -1;
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
if (k != 0) sum %= k;
if (mp.find(sum) != mp.end()) {
if (i - mp[sum] > 1) return true;
} else {
mp[sum] = i;
}
}
return false;
}
};
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int curr_sum = nums[0];
int max_sum = nums[0];
int length = nums.size();
for (int i = 1;i<length;i++){
curr_sum = max(nums[i],curr_sum+nums[i]);
max_sum = max(curr_sum,max_sum);
}
return max_sum;
}
private:
int max(int s1,int s2){
if(s1>=s2)
{
return s1;
}
else{
return s2;
}
}
};
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
cur_num = max_num = nums[0]
for i in range(1,len(nums)):
cur_num = max(nums[i],cur_num+nums[i])
max_num = max(cur_num,max_num)
return max_num
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = INT_MIN, imax = 1, imin = 1;
for(int i=0; i<nums.size(); i++){
if(nums[i] < 0){
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = max(imax*nums[i], nums[i]);
imin = min(imin*nums[i], nums[i]);
res = max(res, imax);
}
return res;
}
};
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n=len(nums)
max_res=-float("inf")
max_num=1
min_num=1
for i in range(n):
if(nums[i]<0):
max_num,min_num=min_num,max_num
max_num=max(max_num*nums[i],nums[i])
min_num=min(min_num*nums[i],nums[i])
max_res=max(max_num,max_res)
return max_res
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述：
对应每个测试案例，输出两个数，小的先输出。
对于一个数组，我们可以定义两个指针，一个从左往右遍历（pleft），另一个从右往左遍历（pright）。首先，我们比较第一个数字和最后一个数字的和curSum与给定数字sum，如果curSum < sum，那么我们就要加大输入值，所以，pleft向右移动一位，重复之前的计算；如果curSum > sum，那么我们就要减小输入值，所以，pright向左移动一位，重复之前的计算；如果相等，那么这两个数字就是我们要找的数字，直接输出即可。
这么做的好处是，也保证了乘积最小。
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> result;
int length = array.size();
if(length < 1){
return result;
}
int pright = length - 1;
int pleft = 0;
while(pright > pleft){
int curSum = array[pleft] + array[pright];
if(curSum == sum){
result.push_back(array[pleft]);
result.push_back(array[pright]);
break;
}
else if(curSum < sum){
pleft++;
}
else{
pright--;
}
}
return result;
}
};
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
if len(array) <= 1:
return []
left, right = 0, len(array)-1
while left < right:
if array[left] + array[right] == tsum:
return array[left], array[right]
elif array[left] + array[right] < tsum:
left += 1
else:
right -= 1
return []
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
虑给定 nums 数组的每个可能的子数组，找到每个子数组的元素总和，并检查使用给定 k 获得的总和是否相等。当总和等于 k 时，我们可以递增用于存储所需结果的 count
class Solution {
public:
int subarraySum(vector<int>& nums, int
