子数组之和

墨蓝 2022-09-24 14:17 191阅读 0赞

## 蛮力法 ##

时间复杂度O(N2).

vector<int> subarraySum(vector<int> nums){
            // write your code here
            vector<int> res;
            int i,j,sum;
            for(i=0;i<nums.size();i++)
            {
                sum=nums[i];
                if(sum==0){
                    res.push_back(i);
                    res.push_back(i);
                    return res; 
                }
                for(j=i+1;j<nums.size();j++)
                {
                   sum+=nums[j];
                   if(sum==0)
                    {
                        res.push_back(i);
                        res.push_back(j);
                        return res;
                    }
                }
            }
            return res;
        }

## 巧妙解法 ##

时间复杂度为O(nlogn)  
思路思路：

> 已知 ：  
> sum\[ i \]=a\[ 0 \]+……a\[ i \];  
> sum\[ j \]=a\[ 0 \]+……a\[ j \];  
> 且 i < j;  
> 如果sum\[ i \]==sum\[ j \]  
> 那么 a\[ i+1 \]+..a\[ j \]==0;

vector<int> subarraySum(vector<int> nums){
            // write your code here
            vector<pair<int,int>> hash(nums.size()+1);
            vector<int> res;
            int i,j,sum=0;
            if(nums.empty())
                return res;
    
            for(i=0;i<nums.size();i++)
            {
                sum+=nums[i];
                hash[i+1].first=sum;
                hash[i+1].second=i+1;
            }
            sort(hash.begin(),hash.end());
            for(i=1;i<hash.size();i++)
            {
                if(hash[i].first==hash[i-1].first)
                {
                    res.push_back(hash[i-1].second);
                    res.push_back(hash[i].second-1);
                    return res;
                }
            }
            return res;
        }

详细的完了补。。。。

发表评论取消回复

表情：

评论列表（有 0 条评论，191人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-1191 K 次串联后最大子数组之和

*题目描述：** 给你一个整数数组 `arr` 和一个整数 `k`。首先，我们要对该数组进行修改，即把原数组 `arr` 重复 `k` 次。 > 举个例子，如果 ...

╰+攻爆jí腚メ/ 2024年04月19日 08:17/ 0 赞/ 105 阅读

相关用foreach求数组之和

当使用foreach循环来计算数组中元素的和时，你可以遵循以下更详细的步骤：创建数组：首先，创建一个包含要计算和的元素的数组。这些元素可以是整数、浮点数或其他数值类型。

╰+攻爆jí腚メ/ 2024年02月20日 09:50/ 0 赞/ 96 阅读

相关如何求出最大子数组之和

问题描述：一个有n个元素的数组，元素中有正有负，数组中一个或者连续多个元素可以组成一个子数组，求子数组中和最大的？方法一：暴力法 > 三层循环，找出所有的子数组，并求

野性酷女/ 2023年07月04日 12:46/ 0 赞/ 18 阅读

相关【数组】两数之和

[【2020秋招-面试题目汇总（随时更新）】][2020_-] 1. 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naG

小鱼儿/ 2022年11月26日 07:56/ 0 赞/ 214 阅读

相关 C语言重构【1191】K 次串联后最大子数组之和

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

约定不等于承诺〃/ 2022年11月06日 15:00/ 0 赞/ 516 阅读

相关子数组之和

蛮力法时间复杂度O(N2). vector<int> subarraySum(vector<int> nums){ // write

墨蓝/ 2022年09月24日 14:17/ 0 赞/ 192 阅读

相关【数组】---1. 两数之和

【题目】两数之和 [题目链接][Link 1] 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，

╰半夏微凉°/ 2022年09月06日 04:55/ 0 赞/ 198 阅读

相关【LintCode 简单】138. 子数组之和

1.问题描述：给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。 2.样例：给出 `[-3, 1, 2, -3, 4]

ゞ浴缸里的玫瑰/ 2022年06月01日 00:10/ 0 赞/ 250 阅读

相关 [LintCode] Continuous Subarray Sum 连续子数组之和

Given an integer array, find a continuous subarray where the sum of numbers is the bigge

短命女/ 2022年02月01日 09:15/ 0 赞/ 222 阅读

相关 LeetCode-数组-三数之和

题目描述给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组

ゝ一世哀愁。/ 2022年01月20日 05:25/ 0 赞/ 211 阅读