lcp352

6909. 最长奇偶子数组

方法一：暴力枚举

class Solution {
   public int longestAlternatingSubarray(int[] nums, int threshhold) {
        // dp
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] % 2 != 0 || nums[i] > threshhold)
                continue;
            int len = 1, pre = 0;
            res = Math.max(res, len);
            for (int j = i + 1; j < n; ++j) {
                if (pre == 0) {
                    if (nums[j] % 2 == 1 && nums[j] <= threshhold) {
                        ++len;
                        pre = 1;
                        res = Math.max(res, len);
                    } else {
                        break;
                    }
                } else { // pre == 1
                    if (nums[j] % 2 == 0 && nums[j] <= threshhold) {
                        ++len;
                        pre = 0;
                        res = Math.max(res, len);
                    } else {
                        break;
                    }
                }
            }
        }
        return res;
    }
}

方法二：一轮遍历

class Solution {
    public int longestAlternatingSubarray(int[] nums, int threshold) {
        int res = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] % 2 == 0 && nums[i] <= threshold) {
                int pre = nums[i] % 2, j = i + 1;
                for (; j < nums.length; ++j) {
                    if (nums[j] % 2 != pre && nums[j] <= threshold)
                        pre = nums[j] % 2;
                    else
                        break;
                }
                res = Math.max(res, j - i);
            }
        }
        return res;
    }
}

6916. 和等于目标值的质数对

方法一：埃氏筛

静态代码块: 静态代码块定义在类中方法外, 静态代码块在非静态代码块之前执行(静态代码块—>非静态代码块—>构造方法)。 该类不管创建多少对象，静态代码块只执行一次.

class Solution {
    private final static int MAX = (int) 1e6;
    private final static boolean[] isPrime = new boolean[MAX + 1];
    private final static int[] prime = new int[MAX];
    static {
        int index = 0;
        for (int i = 2; i <= MAX; ++i) {
            if (!isPrime[i]) {
                prime[index++] = i;
                if (i < MAX / i)
                    for (int j = i * i; j < MAX; j += i)
                        isPrime[j] = true;
            }
        }
    }
    
    public List<List<Integer>> findPrimePairs(int n) {
        List<List<Integer>> res = new LinkedList<>();
        for (int x : prime) {
            int y = n - x;
            if (y < x)
                break;
            if (!isPrime[y])
                res.add(Arrays.asList(x, y));
        }
        return res;
    }
}

204. 计数质数

埃氏筛

class Solution {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        int res = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i]) {
                ++res;
                if ((long) i * i < n)
                    for (int j = i * i; j < n; j += i)
                        isPrime[j] = false;
            }
        }
        return res;
    }
}

6911. 不间断子数组

滑动窗口

map.lastKey() - map.firstKey()得到最大值与最小值的差

res += (long) i - j + 1十分巧妙，举例nums=[5, 4, 2, 4]

1. i = 0， [5]， res += 1 = 1
2. i = 1，[5, 4], [4], res +=2 = 3
3. i = 2, [4, 2], [2] ,res += 2 = 5
4. i = 3, [4,2, 4], [4], [2,4], res += 3 = 8

class Solution {
    public long continuousSubarrays(int[] nums) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int n = nums.length;
        long res = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            while (j <= i && map.lastKey() - map.firstKey() > 2) {
                map.put(nums[j], map.getOrDefault(nums[j], 0) - 1);
                if (map.get(nums[j]) == 0)
                    map.remove(nums[j]);
                ++j;
            }
            res += (long) i - j + 1;
        }
        return res;
    }
}

1438. 绝对差不超过限制的最长连续子数组

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int n = nums.length, res = 0;	
        for (int i = 0, j = 0; i < n; ++i) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            while (j <= i && map.lastKey() - map.firstKey() > limit) {
                map.put(nums[j], map.get(nums[j]) - 1);
                if (map.get(nums[j]) == 0)
                    map.remove(nums[j]);
                ++j;
            }
            res = Math.max(res, i - j + 1);
        }
        return res;
    }
}

6894. 所有子数组中不平衡数字之和

class Solution {
    public int sumImbalanceNumbers(int[] nums) {
        int res = 0, n = nums.length;
        boolean[] visited = new boolean[n + 2];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(visited, false);
            int count = 0;
            visited[nums[i]] = true;
            for (int j = i + 1; j < n; ++j) {
                if (!visited[nums[j]]) {
                    ++count;
                    if (visited[nums[j] - 1])
                        --count;
                    if (visited[nums[j] + 1])
                        --count;
                    visited[nums[j]] = true;
                }
                res += count;
            }
        }
        return res;
    }
}