算法入门第五天

438. 找到字符串中所有字母异位词

还是要使用欠账法，效率高，我自己写的只能打败20%。。

经测试，此方法也适用于567题解答

/**
 438. 找到字符串中所有字母异位词
 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。



 示例 1:

 输入: s = "cbaebabacd", p = "abc"
 输出: [0,6]
 解释:
 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 示例 2:

 输入: s = "abab", p = "ab"
 输出: [0,1,2]
 解释:
 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。


 提示:

 1 <= s.length, p.length <= 3 * 10^4
 s 和 p 仅包含小写字母

 * @author zeroheart
 *
 */
public class Question438 {
    public static List<Integer> findAnagrams(String s, String p) {
        // 经测试，此方法也适用于567题解答

        ArrayList<Integer> ans = new ArrayList<>();
        if (s.length() < p.length()) {
            return ans;
        }

        int[] counts = new int[26]; // 欠账表：欠的字符 -> 欠的个数
        int all = p.length(); // 总欠账数目
        // 统计欠账，生成欠账表:
        for (char c : p.toCharArray()) {
            counts[c-'a']++;
        }

        // 【滑动窗口】还账：
        int l = 0, r = 0, n = s.length();
        char[] str = s.toCharArray();

        while(l < n){
            while(r<n && counts[str[r] - 'a'] > 0){
                all--;
                counts[str[r] - 'a']--;
                r++;
            }

            if(all == 0){
                ans.add(l);
            }

            all++;
            counts[str[l] - 'a']++;
            l++;
        }

        return ans;

        // 滑动窗口，自己写的效率不高
        //        List res = new ArrayList();
        //        int[] stat = new int[26];
        //        char[] sc = s.toCharArray();
        //        char[] pc = p.toCharArray();
        //        for(int i = 0; i<pc.length; i++){
        //            char pci = pc[i];
        //            stat[pci-'a']++;
        //        }
        //
        //        for(int i = 0; i <= sc.length - pc.length; i++){
        //            int[] stati = Arrays.copyOf(stat, stat.length);
        //            int flag = 1;
        //            for(int j = 0; j<pc.length; j++){
        //                char scij = sc[i+j];
        //                if(stati[scij - 'a'] == 0){
        //                    flag = 0;
        //                    break;
        //                }else {
        //                    stati[scij - 'a']--;
        //                }
        //            }
        //            if(flag==1){
        //                res.add(i);
        //            }
        //        }
        //
        //        return res;
    }

    public static void main(String[] args) {
        //System.out.println(findAnagrams("cbaebabacd","abc"));
        System.out.println(findAnagrams("abab","ab"));
    }
}

713. 乘积小于K的子数组

对于abc，增加了d之后，新增加的可能性为d,cd,bcd,abcd = r – l + 1;

/**
 713. 乘积小于K的子数组
 给定一个正整数数组 nums和整数 k 。

 请找出该数组内乘积小于 k 的连续的子数组的个数。



 示例 1:

 输入: nums = [10,5,2,6], k = 100
 输出: 8
 解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
 需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
 示例 2:

 输入: nums = [1,2,3], k = 0
 输出: 0


 提示:

 1 <= nums.length <= 3 * 10^4
 1 <= nums[i] <= 1000
 0 <= k <= 10^6


 * @author zeroheart
 *
 */
public class Question713 {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // 对于abc，增加了d之后，新增加的可能性为d,cd,bcd,abcd = r - l + 1;

        if(k<=1){
            return 0;
        }

        int len = nums.length;
        int left = 0;
        int res = 0;
        int pre = 1;
        for(int i = 0; i<len; i++){
            pre = pre * nums[i];
            while (pre >= k){
                pre = pre / nums[left];
                left++;
            }
            res += i - left + 1;
        }

        return res;
    }

    public static void main(String[] args) {
    }
}

209. 长度最小的子数组

/**
 209. 长度最小的子数组
 给定一个含有 n 个正整数的数组和一个正整数 target 。

 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。



 示例 1：

 输入：target = 7, nums = [2,3,1,2,4,3]
 输出：2
 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 示例 2：

 输入：target = 4, nums = [1,4,4]
 输出：1
 示例 3：

 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 输出：0


 提示：

 1 <= target <= 10^9
 1 <= nums.length <= 10^5
 1 <= nums[i] <= 10^5


 进阶：

 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

 * @author zeroheart
 *
 */
public class Question209 {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int res = Integer.MAX_VALUE;
        int pre = 0;
        int length = nums.length;
        for(int i = 0; i<length; i++){
            pre += nums[i];
            while (pre>=target){
                res = Math.min(res, i - left + 1); // 放在前面
                pre = pre - nums[left];
                left++;
            }
        }

        return res>length ? 0:res;
    }

    public static void main(String[] args) {
    }
}