2022-06-01
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
andp
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
}
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
}
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