Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.
Examples:
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33 Ouptut: Sum found between indexes 2 and 4 Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7 Ouptut: Sum found between indexes 1 and 4 Input: arr[] = {1, 4}, sum = 0 Output: No subarray found
There may be more than one subarrays with sum as the given sum. The following solutions print first such subarray.
public boolean subArraySumK(int[] A, int k) { int n = A.length; if(n == 0) return false; int start = 0, sum = 0; for(int i=0; i<n; i++) { sum += A[i]; while(sum > k && start < i) { sum -= A[start++]; } if(sum == k) { System.out.println("find subarray from "+start +" to " + i); return true; } } System.out.println("no subarray found"); return false; }
Time complexity of this method looks more than O(n), but if we take a closer look at the program, then we can figure out the time complexity is O(n). We can prove it by counting the number of operations performed on every element of arr[] in worst case. There are at most 2 operations performed on every element: (a) the element is added to the curr_sum (b) the element is subtracted from curr_sum. So the upper bound on number of operations is 2n which is O(n).
Reference:
相关推荐
最大子数组总和问题给定一个整数数组,找到一个具有最大和的序列。 看一个例子: let array = [ 1 , - 1 , 5 , 3 , - 7 , 4 , 5 , 6 , - 100 , 4 ]function largestSubarraySum ( array ) { // code to write here}...
matlab开发-subarray。从数组中提取子数组。用于功能输出。
最大子数组总和maximum subarray sum使用Java语言中的所有复杂度来计算子数组的最大和。 1.O(n ^ 3) 2.O(n ^ 2) 3.O(n)
word源码java 玩儿转算法面试 - 课程学习笔记 课程的学习笔记。 课程笔记目录 第一章:算法面试到底是什么鬼 第二章:面试中的复杂度分析 第三章:数组中的问题其实最常见 ...Subarray Sum 3-8 在滑动窗口中做记
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组...
子阵列划分的root-music algorithm
number of subarray whose sum is S using dynamic programming
最大子数组总和 问题 给定一个整数数组,找到一个具有最大和的序列。 例如,看下面的例子。 let array = [ 1 , - 1 , 5 , 3 , - 7 , 4 , 5 , 6 , - 100 , 4 ] function largestSubarraySum ( array ) { ...
leetcode双人赛 1. Pattern: ...given sum (easy) Longest Substring with K Distinct Characters (medium) Fruits into Baskets (medium) No-repeat Substring (hard) Longest Substring with Same Le
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的子数组。如果存在该子数组返回true,否则返回false。 #include #include using namespace std; int main() { std::cout <... subset[i
lru cache leetcode leetcode 记录自己刷leetcode时...subarray-sum-equals-k binary-tree-preorder-traversal n-queens-ii populating-next-right-pointers-in-each-node sum-root-to-leaf-numbers best-time-to-buy
import SubarrayProxy from 'ember-subarray-proxy' ; var slice = SubarrayProxy . create ( { content : Ember . A ( [ 'a' , 'b' , 'c' ] ) , limit : 2 } ) ; slice . get ( 'length' ) // 2 slice . get ( '...
npm install max-subarray bower install max-subarray 用法 const maxSubarray = require ( 'max-subarray' ) ; console . log ( maxSubarray ( [ 1 , - 4 , 1 , 3 , 6 , - 2 , - 9 ] ) ) ; // [1, 3, 6] console ....
1.图案:推拉窗 大小为K的最大总和子数组(简单) 具有给定总和的最小子数组(简单) 最长的具有K个不同字符的子字符串(中) 水果入篮(中) 不重复子字符串(硬)* 替换后具有相同字母的最长子字符串(硬) ...
Play-with-Algorithms 基本的算法和数据结构 来自liuyubobobo老师的课程 章节 讲解例题 课程练习题 更多扩展练习 难题推荐 第一章 算法面试到底是什么鬼? [无] [无] 第二章 面试中的复杂度分析 [无] [无] 第三章 ...
389 | [Find the Difference](https://leetcode.com/problems/find-the-difference/) | [C++](./C++/find-the-difference.cpp) [Python](./Python/find-the-difference.py) | _O(n)_ | _O(1)_ | Easy | | ...
希望更多的人能和我一样,把本狂想曲系列中的任何一道面试题当做一道简单的编程题或一个实质性的问题来看待,在阅读本狂想曲系列的过程中,希望你能尽量暂时放下所有有关面试的一切包袱,潜心攻克每一道“编程题”,...
Subarray Sum 209 3 438 76 第二章 查找表相关问题 2-1 set的使用 Intersection of Two Arrays 349 2-2 map的使用 Intersection of Two Arrays II 350 2-3 set和map不同底层实现的区别 349 350 136 242 202 290 205 ...
leetcode 2 code_interview leetcode和lintcode的一些题目的解法 是剑指offer 是面试中遇到的有意思的题目总结,...138-Subarray-Sum integer-arr 整型数组 值得回顾的题 41-first-missing-positive 01-Two-Sum 求解第K
Longest Subarray Length小程序测试根据给定的k计算最长子数组长度