`

Google&Facebook Interview - Find subarray with given sum

 
阅读更多

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:

http://www.geeksforgeeks.org/find-subarray-with-given-sum/

分享到:
评论

相关推荐

    c语言-leetcode题解之0560-subarray-sum-equals-k

    c语言入门 c语言_leetcode题解之0560_subarray_sum_equals_k

    java-leetcode题解之Continuous Subarray Sum.java

    而Continuous Subarray Sum是LeetCode上的一道中等难度的算法题目。这道题目的核心在于找出数组中和为指定数值的连续子数组,并返回子数组的起始和结束索引。解决这个问题可以采用多种方法,如暴力法、动态规划、...

    java-leetcode题解之Maximum Subarray Sum with One Deletion.java

    Java实现LeetCode题解的“Maximum Subarray Sum with One Deletion”问题的解决方案涉及动态规划的高级应用。该问题要求编写一个函数,找出在删除一个元素的情况下,一个整数数组中的最大子序列和。 在解决这个问题...

    postgrad-challenge-largest-subarray-sum-nyc-web-career-040119

    最大子数组总和问题给定一个整数数组,找到一个具有最大和的序列。 看一个例子: let array = [ 1 , - 1 , 5 , 3 , - 7 , 4 , 5 , 6 , - 100 , 4 ]function largestSubarraySum ( array ) { // code to write here}...

    C语言-leetcode题解之53-maximum-subarray.c

    在C语言的编程领域中,LeetCode题解之53-maximum-subarray.c是一份具有极高参考价值的文档,它深入剖析了如何在C语言环境下实现寻找最大子数组和的问题,通常被称作“最大子序和”问题。这类问题在算法学习和编程...

    python-leetcode题解之152-Maximum-Product-Subarray.py

    代码示例中的Python-leetcode题解之152-Maximum-Product-Subarray.py,提供了一种简洁且高效的解决方案。通过简单的测试用例,可以验证代码的正确性。该题解为学习动态规划以及Python编程提供了很好的实践机会,并且...

    C++-leetcode题解之1310-XOR-Queries-of-a-Subarray.cpp

    该题目编号为1310,标题为“XOR Queries of a Subarray”。解题过程中我们主要利用了异或运算的性质和前缀异或数组的概念来高效解决问题。 异或运算(XOR)是一个重要的位运算符,在C++中表示为'^'。它遵循以下基本...

    js-leetcode题解之152-maximum-product-subarray.js

    在解决LeetCode上的第152题“乘积最大子数组”时,JavaScript是一种常用的编程语言。该问题要求在给定的整数数组中找到一个连续子数组,使得这个子数组中所有数的乘积最大。为了解决这个问题,我们需要考虑数组中...

    matlab开发-subarray

    在MATLAB中,`subarray`是一个非常重要的概念,它涉及到数组操作的核心部分。当我们处理大型数据集时,经常需要从大数组中提取出一部分,也就是子数组,来进行特定的计算或分析。`subarray`操作允许我们有效地访问和...

    maximum-subarray-sum-:Java中的最大子数组总和

    最大子数组和问题是一个经典的计算机科学问题,它在算法设计和数据结构领域有着广泛的应用。在Java编程中,解决这个问题可以采用多种不同的方法,每种方法都有其特定的时间复杂度。下面将详细介绍三种不同时间复杂度...

    js-leetcode题解之53-maximum-subarray.js

    《LeetCode题解之53题:最大子序和》这篇文章,主要围绕着如何用JavaScript解决一个经典的动态规划问题——最大子序和问题。文章首先会对问题进行描述,然后详细讲解如何通过算法逻辑去实现解决方案,并给出相关的...

    word源码java-Play-with-Algorithm-Interview-Learningnotes:Play-with-Algori

    word源码java 玩儿转算法面试 - 课程学习笔记 课程的学习笔记。 课程笔记目录 第一章:算法面试到底是什么鬼 第二章:面试中的复杂度分析 第三章:数组中的问题其实最常见 ...Subarray Sum 3-8 在滑动窗口中做记

    leetcode答案-easy_Maximum-Subarray:easy_Maximum-Subarray

    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-for-subarray.zip_ROOT_root-music_root——music_sub arra

    子阵列划分的root-music algorithm

    Grokking-the-Coding-Interview-Patterns-for-Coding-Questions

    1.图案:推拉窗 大小为K的最大总和子数组(简单) 具有给定总和的最小子数组(简单) 最长的具有K个不同字符的子字符串(中) 水果入篮(中) 不重复子字符串(硬)* 替换后具有相同字母的最长子字符串(硬) ...

    largest-subarray-sum-v-000

    最大子数组总和 问题 给定一个整数数组,找到一个具有最大和的序列。 例如,看下面的例子。 let array = [ 1 , - 1 , 5 , 3 , - 7 , 4 , 5 , 6 , - 100 , 4 ] function largestSubarraySum ( array ) { ...

    leetcode双人赛-LeetCode:力码

    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

    动态规划-Subarray Sum Equals K-子数组和为K

    给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的子数组。如果存在该子数组返回true,否则返回false。 #include #include using namespace std; int main() { std::cout &lt;... subset[i

    Subarray_SUM_dynamicprogramming_

    在这个特定的题目"Subarray SUM dynamicprogramming_"中,我们关注的是找出一个数组中和为S的所有子数组的数量,这个问题可以通过动态规划有效地解决。下面我们将深入探讨这个话题。 首先,我们需要了解什么是子...

Global site tag (gtag.js) - Google Analytics