# 2022-06-01

## 438. Find All Anagrams in a String

### Description

Given two strings `s` and `p`, return an array of all the start indices of `p`'s anagrams in `s`. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

``````Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".``````

Example 2:

``````Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".``````

Constraints:

• `1 <= s.length, p.length <= 3 * 104`

• `s` and `p` consist of lowercase English letters.

### Solution

#### Approach #0

``````func findAnagrams(s string, p string) (ans []int) {
target, current := make([]int, 26), make([]int, 26)
count := 0
for _, ch := range p {
target[ch-'a']++
}
for _, t := range target {
if t != 0 {
count++
}
}
i, j, sig := 0, 0, 0
for j < len(s) {
in := s[j] - 'a'
j++
if target[in] > 0 {
current[in]++
if target[in] == current[in] {
sig++
}
}
for j-i >= len(p) {
if sig == count {
ans = append(ans, i)
}
out := s[i] - 'a'
i++
if target[out] > 0 {
if current[out] == target[out] {
sig--
}
current[out]--
}
}
}
return ans
}``````

## 713. Subarray Product Less Than K

### Description

Given an array of integers `nums` and an integer `k`, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than `k`.

Example 1:

``````Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.``````

Example 2:

``````Input: nums = [1,2,3], k = 0
Output: 0``````

Constraints:

• `1 <= nums.length <= 3 * 10^4`

• `1 <= nums[i] <= 1000`

• `0 <= k <= 10^6`

### Solution

#### Approach #0

``````func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
cur := 1
i, j := 0, 0
for i < len(nums) {
if j >= len(nums) {
cur = 1
i++
j = i
continue
}
in := nums[j]
if cur*in < k {
ans++
cur = cur * in
j++
} else {
cur = 1
i++
j = i
}
}
return ans
}``````

#### Approach #1

``````func numSubarrayProductLessThanK(nums []int, k int) (ans int) {
i, cur := 0, 1
for j, num := range nums {
cur *= num
for ; i <= j && cur >= k; i++ {
cur /= nums[i]
}
ans += j - i + 1
}
return
}``````

## 209. Minimum Size Subarray Sum

### Description

Given an array of positive integers `nums` and a positive integer `target`, return the minimal length of a contiguous subarray `[numsl, numsl+1, ..., numsr-1, numsr]` of which the sum is greater than or equal to `target`. If there is no such subarray, return `0` instead.

Example 1:

``````Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.``````

Example 2:

``````Input: target = 4, nums = [1,4,4]
Output: 1``````

Example 3:

``````Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0``````

Constraints:

• `1 <= target <= 10^9`

• `1 <= nums.length <= 10^5`

• `1 <= nums[i] <= 10^5`

Follow up: If you have figured out the `O(n)` solution, try coding another solution of which the time complexity is `O(n log(n))`.

### Solution

#### Approach #0

``````func minSubArrayLen(target int, nums []int) (ans int) {
ans = len(nums) + 1
i, cur := 0, 0
for j, num := range nums {
cur += num
for ; i <= j && cur >= target; i++ {
if cur >= target {
ans = min(ans, j-i+1)
}
cur -= nums[i]
}
}
if ans == len(nums)+1 {
ans = 0
}
return
}

func min(a, b int) int {
if a < b {
return a
}
return b
}``````

Last updated