网站建设有生意吗,建站及推广,家庭网站建设,网上售卖平台有哪些138-子数组之和 给定一个整数数组#xff0c;找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置 注意事项 There is at least one subarray that its sum equals to zero. 样例 给出 [-3, 1, 2, -3, 4]#xff0c;返回[0, 2] 或者 [1, 3]. 标签 子数…138-子数组之和 给定一个整数数组找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置 注意事项 There is at least one subarray that its sum equals to zero. 样例 给出 [-3, 1, 2, -3, 4]返回[0, 2] 或者 [1, 3]. 标签 子数组 哈希表 方法一O(n^2) 利用两个for循环每次取出一个元素依次与后面的元素相加时间复杂度是O(n^2) code class Solution {
public:/*** param nums: A list of integers* return: A list of integers includes the index of the first number * and the index of the last number*/vectorint subarraySum(vectorint nums){// write your code hereint size nums.size(), sum 0;if(size 0) {return vectorint();}vectorint result;for(int i0; isize; i) {sum nums[i];if(sum 0){result.push_back(i);result.push_back(i);return result;}for(int ji1; jsize; j) {sum nums[j];if(sum 0) {result.push_back(i);result.push_back(j);return result;}}}return result;}
}; 方法二O(n) 利用一个 map 记录从第一个元素开始到当前元素之和 与 当前元素的下标 的对应关系若有一段子数组和为0那么势必出现同一和对应2个下标此时就找到了和为零的连续序列时间复杂度是O(n) code class Solution {
public:/*** param nums: A list of integers* return: A list of integers includes the index of the first number * and the index of the last number*/vectorint subarraySum(vectorint nums){// write your code hereint size nums.size(), sum 0;if(size 0) {return vectorint();}vectorint result;mapint, int subSum;subSum[0] -1;for(int i0; isize; i) {sum nums[i];if(subSum.count(sum)) {result.push_back(subSum[sum] 1);result.push_back(i);return result;}subSum[sum] i;}return result;}
}; 转载于:https://www.cnblogs.com/libaoquan/p/7223043.html
