昨天做了个获取数组长度的题很有意思
如果你想知道什么题? 既然你诚心诚意的发问了, 我就大发慈悲的告诉你!
给定一个正整数的数组, 给定个正整数, 求正整数数组, 找出最小的连续数组使得相加之和>=给定的正整数, 没有返回0
例如 arr = [2, 3, 1, 2, 4, 3] , s = 7, 返回 [4, 3]
双循环
双循环, 暴力法是一个比较好理解的方法, 适合新手
- 数组如果包含给定值 s, 直接弹出
- 创建个初始的最小值
- 第一层循环: 依次循环初始位 sum[i]
- 第二层循环: i 之后的数字sum[j], 循环并相加, >= 给定值 s 时候判断 j-i+1 是否小于最小值min,
- 如果小, min为 j-i+1, 否则 min还是之前值
- 循环之后返回最小值
这里有几个点要注意一下
① 循环第二层j时, 如果找到>= s的时候,直接break, 减少不必要循环,
为什么呢? 因为再加已经没有意义, 我们找到的是 "长度最小的连续子数组", 而不是循环到底, 减少一定时间复杂度
② 留意初始设置的最小值min一定要"大"
③ 针对特殊情况, 数组包含s 特殊处理
swift
func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
// 如果数组包含s, 直接返回1, 包含最小长度即为1
if nums.contains(s) {
return 1
}
// 设置初始值min, 最小值要大于数组长度, 我这里设置最小值为: 数组长度+1
// 小于的话会影响for下面判断, 不好处理
// 等于的话要单独处理 数组之和全加完 >= s 情况
var min = nums.count + 1
// 开始循环数组
for i in 0..<nums.count {
// 设置初始和 sum 值为0
var sum = 0
for j in i..<nums.count {
// 第二层循环, 依次累加
sum = sum + nums[j]
// 判断如果和大于等于s了, 弹出第二层循环, 再加也没有意义
if(sum >= s){
//三目运算符 赋值min
min = (j-i+1)<min ? (j-i+1):min
break;
}
}
}
// 返回min, 如果min为初始值返回0
return min==nums.count+1 ? 0:min;
}
可看到, 这种方法节省空间复杂度, 但是在时间复杂度上却很耗, 由于双循环会使得时间复杂为O(n^2)
我更建议针对数据量小, 对内存消耗要求要低的情况下使用
双指针
双指针方法即: 定义两个指针, 循环开始位start, 循环结束位置end
循环判断 start位, end位 之间的元素和,
如果小于给定值s, end向右移动一位
如果大于给定值s, start向右移动一位,
依次判断 end - start + 1 与 min 的最小值赋给新的min, 最后返回最小 min
swift
func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
// 如果数组包含指定元素直接返回1
if nums.contains(s) {
return 1
}
// 定义初始值low high sum
var low = 0, high = 0, sum = 0
// 定义初始值min 大于数组长度即可
var min = nums.count + 1
// 循环high指针
while high < nums.count {
// 总和加最新 nums[high]
sum += nums[high]
// 循环low指针
while sum >= s {
// 取 min 和 high-low+1 的最小值 赋给新的 min
min = (high-low+1)<min ? (high-low+1):min
// 总和去掉之前的 nums[low]
sum = sum - nums[low]
// low向右移一位
low += 1
}
// high向右移一位
high += 1
}
// 三目运算符返回最小值
return min==(nums.count + 1) ? 0:min;
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
