GeezerVison is showing github.com — leet-code/Java/Subarray Sum II.java at master · awangdev/leet-code

Expand file tree

Subarray Sum II.java

Copy path

More file actions

executable file

29 lines (25 loc) · 779 Bytes

Copy path

executable file

29 lines (25 loc) · 779 Bytes

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

tags: Two Pointers, Array, Binary Search

```

Given an integer array, find a subarray where the sum of numbers is in a given interval.

Your code should return the number of possible answers. (The element in the array should be positive)

Example

Given [1,2,3,4] and interval = [1,3], return 4. The possible answers are:

[0, 0]

[0, 1]

[1, 1]

[2, 2]

Thoughts:

Brutle O(n2) with preSum can do. Do better: O(nlogn)

- presum

- iterate over start point, which will be the 'must have' index in result

- find the largest end point, where preSum[end] - preSum[start - 1] <= max. Binary Search since the presum will be increasing

- count += end - start + 1

- move on to next start

- Overall it should be O(nlogn)

- should write the binary search as a separate function

```