560.和为k的子数组
题目描述
给你一个整数数组 nums
和一个整数 k
,请你统计并返回 该数组中和为 k
的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1:
输入:nums = [1,1,1], k = 2
输出:2
示例 2:
输入:nums = [1,2,3], k = 3
输出:2
提示:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
解题思路
- 遍历所有子数组的左边界和右边界
- 求和区间中的和并判断等不等于k
代码实现
class Solution {
public:int subarraySum(vector<int>& nums, int k) {int ans = 0;for (int i = 0; i < nums.size(); i ++) {int sum = nums[i];if (sum == k) ans ++;for (int j = i + 1; j < nums.size(); j ++) {sum += nums[j];if (sum == k) ans ++;}}return ans;}
};
128.最长连续序列
题目描述
给定一个未排序的整数数组 nums
,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n)
的算法解决此问题。
示例 1:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2:
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
解题思路
- 给数组排序
- 遍历数组,并判断是否连续
- 不连续就更新答案,连续就长度加一
代码实现
class Solution {
public:int longestConsecutive(vector<int>& nums) { int ans = 0;int len = 1;set<int> s;for (auto it = nums.begin(); it != nums.end(); it ++) {s.insert(*it);}for (auto it = s.begin(); it != s.end(); it ++) {if ((next(it) != s.end()) && *next(it) - *it == 1) {len ++;}else {ans = max(ans, len);len = 1;}}return ans;}
};